34. Search for a Range

Use binary search twice for left and right boundary respectively. Instead of checking nums[mid] == target, for left boundary, we only need to move the hi to mid. Note, we shouldn't move hi to mid-1 so that nums[hi] could be equal to target and hi will be the left boundary eventually. Then we can do the same thing to the right boundary but this time we move lo to mid. However, the mid needs to be computed as lo+(hi-lo)/2+1 such that the mid is biased to right. Otherwise, you'll get LTE if input is [2,2] as lo will stay at 0.

1:  class Solution {  
2:  public:  
3:    vector<int> searchRange(vector<int>& nums, int target) {  
4:      vector<int> res(2, -1);  
5:      int lo = 0, hi = nums.size()-1;  
6:      while (lo < hi) {  
7:        int mid = lo + (hi - lo) / 2;  
8:        if (nums[mid] < target) lo = mid + 1;  
9:        else hi = mid;  
10:      }  
11:      if (nums[hi] != target) return res;  
12:      res[0] = hi;  
13:      hi = nums.size()-1;  
14:      while (lo < hi) {  
15:        int mid = lo + (hi - lo) / 2+1;  
16:        if (nums[mid] > target) hi = mid - 1;  
17:        else lo = mid;  
18:      }  
19:      res[1] = lo;  
20:      return res;  
21:    }  
22:  };