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