写在前面:我们主要还是分享算法的模板,而不是去刨析算法的原理!
定义: 二分答案是指在答案具有单调性的前提下,利用二分的思想枚举答案,将求解问题转化为验证结果。 流程: 首先需要估计答案的上下界,然后不断取区间中点进行验证(这就要求答案的验证应当简单可行),并通过验证结果不断更新答案区间,最终得到答案。不难看出,朴素的枚举验证时间复杂度是O(n)的,而二分可以做到O(logn) 特征: 1.答案具有单调性 2.二分答案的问题往往有固定的问法,比如:令最大值最小(最小值最大),求满足条件的最大(小)值等。
在单调递增序列a中查找<=x的数中最大的一个(即x或x的前驱)
while (l < r) {
int mid = (l + r + 1) / 2;
if (a[mid] <= x) l = mid; else r = mid - 1;
}