HHot 100C++ 图解

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

中等 二分查找 4 帧动画 在力扣上做

一句话套路两次边界:lower_bound 与 upper_bound

题目描述

给你一个按照非递减顺序排列的整数数组 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

思路

时间O(log n)
空间O(1)

思路

两次「找边界」。first = lower_bound(target),last = lower_bound(target+1) - 1。找右边界也可以写成 upper_bound。

这就是「target 的取值范围 = [lower_bound(t), upper_bound(t))」。

提醒

target 可能不存在(要判 *it != target),也可能在末尾(+1 会溢出,所以手写时找右边界用 upper_bound 语义而不是 target+1)。

图解

1 0 1 1 1 2 2 3 3 4 3 5 4 6 4 7 4 8 4 9
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/11_binary_search.cpp45 行
namespace lc0034 {
class Solution {
 public:
  // 手写边界版:第一个 >= target 的下标(等于 nums.size() 表示没有)
  static int lowerBound(const vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size();  // 半开区间 [lo, hi)
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      if (nums[mid] < target)
        lo = mid + 1;
      else
        hi = mid;  // mid 可能就是答案
    }
    return lo;
  }

  // 第一个 > target 的下标。用 upperBound 而不是 lowerBound(target+1):
  // 后者在 target == INT_MAX 时会整型溢出(这是本题最阴的坑)。
  static int upperBound(const vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size();
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      if (nums[mid] <= target)
        lo = mid + 1;
      else
        hi = mid;
    }
    return lo;
  }

  vector<int> searchRange(const vector<int>& nums, int target) {
    int first = lowerBound(nums, target);
    if (first == (int)nums.size() || nums[first] != target) return {-1, -1};
    return {first, upperBound(nums, target) - 1};
  }

  // STL 版:一行搞定,写业务代码时优先用它
  static vector<int> searchRangeSTL(const vector<int>& nums, int target) {
    auto lo = std::lower_bound(nums.begin(), nums.end(), target);
    if (lo == nums.end() || *lo != target) return {-1, -1};
    auto hi = std::upper_bound(lo, nums.end(), target);
    return {(int)(lo - nums.begin()), (int)(hi - nums.begin()) - 1};
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q34_find_first_last16 行
lc0034::Solution s;
vector<int> a{5, 7, 7, 8, 8, 10};
CHECK_EQ(s.searchRange(a, 8), vector<int>{3, 4});
CHECK_EQ(s.searchRange(a, 6), vector<int>{-1, -1});
CHECK_EQ(s.searchRange(std::vector<int>{}, 0), vector<int>{-1, -1});
vector<int> b{1};
CHECK_EQ(s.searchRange(b, 1), vector<int>{0, 0});
vector<int> c{2, 2};  // 全部相同
CHECK_EQ(s.searchRange(c, 2), vector<int>{0, 1});
// 手写版与 STL 版必须完全一致
vector<int> d{1, 1, 1, 2, 3, 3, 4, 4, 4, 4};
for (int t = 0; t <= 5; ++t) CHECK_EQ(s.searchRange(d, t), s.searchRangeSTL(d, t));
vector<int> e{INT_MAX - 1, INT_MAX, INT_MAX};  // 验证不会因 target+1 溢出
CHECK_EQ(s.searchRange(e, INT_MAX), vector<int>{1, 2});
vector<int> f{INT_MIN, INT_MIN};
CHECK_EQ(s.searchRange(f, INT_MIN), vector<int>{0, 1});

↑↓ 选择↵ 打开/ 随时唤起