acwing算法基础之基础算法--整数二分算法

1 知识点

有单调性一定可以二分，但在某些情况下，不具有单调性也可以二分。
单调性也可以抽象成某类性质，分界点左边不满足此性质，而右边满足此性质。当然也可以分界点左边满足此性质，而右边不满足此性质。
注意存在边界情况，容易进入死循环，此时需要考虑[0,1]的case去设置mid。

2 代码模板

推荐此通用模板：不需要单调性的整数二分模板（也即，只需要存在分界点，一侧是true，一侧是false）。代码如下所示，

int l = 0, r = n - 1;
int ans = -1; //找到分界点，它亲近check(*)=true。
while (l <= r) {
	int mid = l + r >> 1;
	if (check(mid)) {
		ans = mid;
		l = mid + 1;
	} else {
		r = mid - 1;
	}
}
if (ans == -1) cout << "没有找到分界点！" << endl;
else cout << "找到了分界点！" << endl;
1
2
3
4
5
6
7
8
9
10
11
12
13

//有序向量nums
//请找到第一个大于等于x的下标，相当于lower_bound()
int l = 0, r = nums.size() - 1;
while (l < r) {
	int mid = l + r >> 1;
	if (nums[mid] >= x) { //找到第一个大于等于x的下标，相当于lower_bound()
		r = mid;
	} else {
		l = mid + 1;
	}
}
if (nums[l] == x) {
	cout << "pass" << endl;
} else {
	cout << "failed" << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//有序向量nums
//请找到最后一个小于等于x的下标
int l = 0, r = nums.size() - 1;
while (l <= r) {
	int mid = l + r + 1 >> 1;
	if (nums[mid] <= x) {
		l = mid;
	} else {
		r = mid - 1;
	}
}
if (nums[l] == x) {
	cout << "pass" << endl;
} else {
	cout << "failed" << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16