Learn2Live

随机笔记

leet34. 范围二分查找

8分钟阅读

给你一个按照非递减顺序排列的整数数组 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 <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums 是一个非递减数组
  • -10^9 <= target <= 10^9

思路一

二分法。不过恶心的是要找一个区间，遇到相等的情况，要着重思考。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1,-1};
        if (nums.size() == 1) {
            if (target != nums[0]) return {-1,-1};
            return {0,0};
        }
 
		// 是否贪心往最小索引搜索
        auto bin_search = [&nums, target](int b, int e, bool min) {
            while (b + 1 < e) {
                int m = b + (e - b) / 2;
                // printf("min%d: b%d, m%d, e%d\n", min, b, m , e);
                if (target == nums[m]) {
                    if (min) {
                        if (e != m + 1) e = m + 1;
                        // 最后剩3个数的时候，要小心处理边界，因为边界更新后可能和上一次一模一样，造成死循环
                        else return nums[b] == target ? b : m;
                    } else {
                        b = m;
                    }
                } else if (target < nums[m]) {
                    e = m;
                } else {
                    b = m;
                }
            }
            if (nums[b] == target) return b;
            return -1;
        };
 
        // n >= 2
        const int n = nums.size();
        int beg = bin_search(0, n, true);
        int end = bin_search(0, n, false);
        return {beg, end};
    }
};

思路二：利用 lower_bound 语义

C++ 泛型算法中提供了 lower_bound 和 upper_bound，其含义为

  • lower_bound: 找到序列中不小于（大于等于）目标值的第一个索引
  • upper_bound：找到序列中大于目标值的第一个索引

题目让我们找值为 target 的区间。其实就是找 lower_bound 和 upper_bound 呀。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto start = lower_bound(nums.begin(), nums.end(), target);
        // lowerbound在界外，或lowerbound处不等于target，肯定是大于target。
        // 那么整个数组中不可能存在target了，可以直接返回。
        if (start == nums.end() || *start != target) {
            return {-1, -1};
        }
        // auto end = upper_bound(nums.begin(), nums.end(), target);
        // or
        auto end = lower_bound(nums.begin(), nums.end(), target + 1);
        return {
            static_cast<int>(start - nums.begin()),
            static_cast<int>(end - nums.begin() - 1)
        };
    }
};

手写 lowerbound

lowerbound 说起来也就是个二分。参考灵神的二分法视频教程，写出三种二分区间。

Key Insight

不要像传统二分那样去找答案在哪，而是要把区间之外的元素想清楚。

以闭区间为例，定义区间 [L, R]，我们想要知道区间里面的元素和 target 之间的大小关系。准确说，我们是要知道区间外的元素和 target 之间的大小关系。区间内的元素总是还未访问的。取区间中点 M，如果 ，我们立刻知道

  1. 若 A[M] < target，则 [L, M] 内的元素都小于 target. 把 L 更新为 M + 1.
  2. 否则，[M, R] 内的元素都大于等于 target. 把 R 更新为 M - 1.
  3. 这样一来，新区间 [L, R] 内的元素是未访问过的，我们继续重复上面的步骤，直到区间内没有元素，即我们直到了所有元素和 target 的大小关系。

最终，区间收缩为空。由于我们维护的规则，任意一次循环结束时，总有

  • A[L-1] < target
  • A[R+1] >= target

我们可以称之为循环不变量。因此，我们要找的索引就是 R+1. 又因为退出循环时 L = R + 1，所以也可以将 L 作为答案。

学会这一手，让你的二分不再死循环！

// 左闭右闭
int lowerbound0(vector<int>& nums, int target) {
	int l = 0, r = nums.size() - 1;
	/*维护 L, R 使得
		1. A[L-1] < target
		2. A[R+1] >= target
	*/
	while (l <= r) { // 区间有元素
		int mid = l + (r - l) / 2;
		if (nums[mid] < target) {
			// 此时我知道 mid 及其左边都 < target（染红色）
			// 但 [mid+1, r] 内的元素还未确定大小，
			// 所以 l 更新为 mid+1.
			l = mid + 1;
		} else {
			// 此时我知道 mid 及其右边都满足 >= target（染蓝色）
			// 但是我们区间的定义是“还未和target确定大小关系的集合”，
			// 而非包含最终答案的集合！
			// 而这个区间应该是 [l, mid - 1]，所以 r 更新为 mid-1.
			r = mid - 1;
		}
	} // 目标是 [l,r] 之外均染色，[l,r] 之内均未染色。直到 [l,r] 为空，所有元素都染色。
	return l;
}
 
// 左闭右开
int lowerbound1(vector<int>& nums, int target) {
	int l = 0, r = nums.size();
	/*维护 L, R 使得
		1. A[L-1] < target
		2. A[R] >= target
	*/
	while (l < r) {
		int mid = l + (r - l) / 2;
		if (nums[mid] < target) {
			l = mid + 1;
		} else {
			r = mid;
		}
	}
	return l;
}
 
// 左开右开
int lowerbound1(vector<int>& nums, int target) {
	int l = -1, r = nums.size();
	/*维护 L, R 使得
		1. A[L] < target
		2. A[R] >= target
	*/
	while (l + 1 < r) {
		int mid = l + (r - l) / 2;
		if (nums[mid] < target) {
			l = mid;
		} else {
			r = mid;
		}
	}
	return r;
}

然后套用思路二即可。

lower_bound 转换

如果题目不是让你找第一个大于等于，而是大于/小于/小于等于呢？对于整数数组来说，这些是可以互相转换的。假设我们已经有了一个 lowerbound 函数返回第一个大于等于 x 的索引。那么对于，

  1. > x === lower_bound(x + 1)
  2. < x === lower_bound(x) - 1
  3. <= x ==== lower_bound(x+1) - 1

Reference

强烈建议观看灵神的二分法讲解视频！

关系图谱