34. 搜索范围

• 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
• 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值，返回 [-1, -1]。

示例

示例 1:
  输入: nums = [5,7,7,8,8,10], target = 8
  输出: [3,4]

示例 2:
  输入: nums = [5,7,7,8,8,10], target = 6
  输出: [-1,-1]

思路

1. 二分查找的变形。其本质是要找到最左的 taget 和最右的 target，因此可以二分查找两次，第一次找 lIndex, 第二次找 rIndex。
2. 利用 lower_bound 来实现范围的查找。因为数组全是整数，所以第一次搜索 target 的 lower_bound, 第二次搜索 target + 1 的 lower_bound(减去 1 即为所求的 rIndex)

class Solution_34_01 {
 public:
  vector<int> searchRange(vector<int>& nums, int target) {
    int size = nums.size();
    if (size == 0) return {-1, -1};
    if (size == 1 && nums[0] == target) return {0, 0};
    int left = 0, right = size - 1;
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] > target) {
        right = mid - 1;
      } else if (nums[mid] < target)
        left = mid + 1;
      else {
        right = mid;
      }
    }
    int lIndex = nums[right] == target ? right : -1;
    left = 0, right = size - 1;
    while (left < right) {
      // 此处 +1, 保证 mid 更靠近 right 那边
      int mid = left + (right - left + 1) / 2;
      if (nums[mid] > target) {
        right = mid - 1;
      } else if (nums[mid] < target)
        left = mid + 1;
      else {
        left = mid;
      }
    }
    int rIndex = nums[right] == target ? right : -1;
    return {lIndex, rIndex};
  }
};

class Solution_34_02 {
 public:
  vector<int> searchRange(vector<int>& nums, int target) {
    int lIndex = lower_bound(nums, target);
    int rIndex = lower_bound(nums, target + 1) - 1;
    if (lIndex < nums.size() && nums[lIndex] == target)
      return {lIndex, rIndex};
    else
      return {-1, -1};
  }
  // 很巧妙的写法，求lower_bound
  int lower_bound(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] < target)
        left = mid + 1;
      else
        right = mid - 1;
    }
    return left;
  }
};