9ms C++ using 2 binary searches


  • 0
    S

    Do a seearch for the "lower_bound" i.e. the first element <= the target, followed by the "upper_bound" i.e. the first element > the target.

    vector<int> searchRange(vector<int>& nums, int target) {
      // Find lower bound, first element >= target
      int low = 0, high = nums.size() - 1;
      while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] >= target) {
          high = mid;
        } else {
          low = mid + 1;
        }
      }
            
      if (nums[low] != target) {
        return vector<int>({-1, -1});
      }
            
      int begin = low;
            
      // Find upper bound, last element <= target
      low = 0, high = nums.size() - 1;
      while (low < high) {
        int mid = low + (high - low + 1) / 2;
        if (nums[mid] > target) {
          high = mid - 1;
        } else {
          low = mid;
        }
      }
            
      int end = low;
    
      return vector<int>({begin, end});
    }
    

Log in to reply
 

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