在排序数组中查找元素的第一个和最后一个位置

题面

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入： nums = [5,7,7,8,8,10], target = 8 输出：[3,4]

示例 2：

输入： nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]

示例 3：

输入： nums = [], target = 0 输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

分析

• 朴素的想法是，找到一个 target 值后，就往左右扩展，查找该元素的左右边界

• 但是在最坏情况下（整个数组都是 target），其时间复杂度为 $O(\log n)$​

• 代码实现

  class Solution {
  public:
      vector<int> searchRange(vector<int>& nums, int target) {
          int left = 0, right = nums.size() - 1, mid = 0;
          while (left <= right) {
              mid = left + (right - left) / 2;
              if (nums[mid] < target) {
                  left = mid + 1;
              } else if (nums[mid] > target) {
                  right = mid - 1;
              } else {
                  int leftRange = mid, rightRange = mid;
                  while (leftRange > 0 && nums[leftRange - 1] == target)
                      leftRange--;
                  while (rightRange < nums.size() - 1 &&
                         nums[rightRange + 1] == target)
                      rightRange++;
                  return {leftRange, rightRange};
              }
          }
          return {-1, -1};
      }
  };

• 如何更简单地寻找左右边界？

• 可以实现一个二分查找函数，它返回大于等于 target 的第一个数的下标；显然左边界可以直接确定，那么如何确定右边界？

• 可以找到大于等于 target+1 的第一个数的下标；如果 target+1 存在，那么其下标 -1 就是右边界；如果 target+1 不存在，那么将返回第一个大于 target+1 的元素的下标，显然，其下标 -1 也是右边界

• 如果大于等于 target+1 的元素不存在怎么办？此时该查找函数会返回 n，这时 n-1 也正好是右边界

• 代码如下

  class Solution {
      // lower_bound 返回最小的满足 nums[i] >= target 的下标 i
      // 如果数组为空，或者所有数都 < target，则返回 nums.size()
      // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
      int lower_bound(vector<int>& nums, int target) {
          int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right]
          while (left <= right) { // 区间不为空
              // 循环不变量：
              // nums[left-1] < target
              // nums[right+1] >= target
              int mid = left + (right - left) / 2;
              if (nums[mid] >= target) {
                  right = mid - 1; // 范围缩小到 [left, mid-1]
              } else {
                  left = mid + 1; // 范围缩小到 [mid+1, right]
              }
          }
          // 循环结束后 left = right+1
          // 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
          // 所以 left 就是第一个 >= target 的元素下标
          return left;
      }
  
  public:
      vector<int> searchRange(vector<int>& nums, int target) {
          int start = lower_bound(nums, target);
          if (start == nums.size() || nums[start] != target) {
              return {-1, -1}; // nums 中没有 target
          }
          // 如果 start 存在，那么 end 必定存在
          int end = lower_bound(nums, target + 1) - 1;
          return {start, end};
      }
  };