二分法

手写 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

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