class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ret({1,1});
if(!nums.size()) return ret;
int i = BinSearch(nums, 0, nums.size(), target);
if(i < 0) return ret;
else
{
int j = i, k = i;
while(nums[j] == target && j >= 0);
while(nums[++k] == target && k < nums.size());
ret[0] = j + 1;
ret[1] = k  1;
}
return ret;
}
private:
inline int BinSearch(vector<int>& nums, int lo, int hi, int target)
{
while(lo < hi)
{
int mi = (lo + hi) >> 1;
if(nums[mi] < target) lo = mi + 1;
else if(nums[mi] == target) return mi;
else if(nums[mi] > target) hi = mi;
}
return 1;
}
};
My C++ solution using binary search, 8ms and beats 98.09%


@Cczhang Because leetcode testcases are all too short. Think about a vector of size 1000, with 9998 targets in it, then your O(n) would be much slower than thrice binary search.