C++ binary search solution (lower_bound implementation).

• ``````vector<int> searchRange(vector<int>& nums, int target) {
int idx1 = lower_bound(nums, target);
int idx2 = lower_bound(nums, target+1)-1;
if (idx1 < nums.size() && nums[idx1] == target)
return {idx1, idx2};
else
return {-1, -1};
}

int lower_bound(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1;
while (l <= r) {
int mid = (r-l)/2+l;
if (nums[mid] < target)
l = mid+1;
else
r = mid-1;
}
return l;
}``````

• It is smart to avoid repeating the code by find the end of the range through reusing lower_bound. Simply find the starting index of next number and decrease it by 1.

• @caikehe great job! much tight and clean than mine

Here is my solution, I used a bit slower way but it works.

Step1. Binary search for the target
Step2. Search towards left and right

``````class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left_binary = 0;
int right_binary = nums.size() - 1;
int mid;
int start = -1; //initailize as -1
int end = -1;
vector<int> result;

//Step1. Binary search for the target
while(left_binary <= right_binary)
{
mid = (left_binary + right_binary) / 2;
if(nums[mid] == target)
{
start = end = mid; //record the index
}
if(nums[mid] > target){right_binary = mid - 1;}
else{left_binary = mid + 1;}
}

//Step2. search towards left and right
while(start > 0 && nums[start - 1] == target){ --start;}
while(end < nums.size() - 1 && nums[end + 1] == target){ ++end;}

result.push_back(start);
result.push_back(end);

return result;

}

};
``````

• @tsuih805 My solution is similar to you. But the difference is that I still use binary search to implement step2.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.