二分枚举,也叫二分查找,指的就是给定一个区间,每次选择区间的中点,并且判断区间中点是否满足某个条件,从而选择左区间继续求解还是右区间继续求解,直到区间长度不能再切分为止。
由于每次都是把区间折半,又叫折半查找,时间复杂度为 O(logn),和线性枚举的求解结果一直,但是高效许多,返回值可以是下标,也可以是元素本身。
【例题3】只有两种颜色的数组 arr ,左边部分为红色用 0 表示,右边部分为绿色用 1 表示,要求找到下标最小的绿色元素的下标。
如图所示,下标最小的绿色元素的下标为 3,所以应该返回 3。
算法分析
1)目标
对于这个问题,当我们拿到这个数组的时候,第一个绿色位置在哪里,我们是不知道的,所以,现在的目标就是要通过二分枚举找到红色区域和绿色区域的边界。
2)游标
利用线性枚举的思路,我们引入游标的概念,只不过需要两个游标,左边一个红色游标,右边一个绿色游标。并且游标初始位置都在数组以外,对于一个 n 个元素的数组,红色游标初始位置在 -1,绿色游标初始位置在 n。
3)二分
我们将两个游标相加,并且除 2,从而得到游标的中点,并且判断中点所在位置的颜色,发现是绿色的,这说明从 中点游标 到 绿色游标 的元素都是绿色的。如下图所示:
于是,我们可以把 绿色游标 替换成 中点游标,如下图所示:
这样就完成了一次二分,区间相比之前,缩小了一半。注意,我们要求的解,一定永远在 红色游标 和 绿色游标 之间。
然后,我们继续将两个游标相加,并且除 2,从而得到游标的中点,并且判断中点所在位置的颜色,发现是红色的,这说明从 红色游标 到 中点游标 的元素都是红色的。如下图所示:
于是,我们可以把 红色游标 替换成 中点游标 ,如下图所示:
同样上述算法,再经过两次二分以后,我们得到了如下结果:
这个时候,这个时候 红色游标 和 绿色游标 的位置一定相差 1,并且 绿色游标 的位置就是我们这个问题要求的解。
二分查找模版
int binarySearch(int *arr, int arrSize, int x) {
int l = -1, r = arrSize; // (1)
int mid;
while(r - l > 1) { // (2
mid = l + (r - l) / 2; // (3)
if( isGreen(arr[mid], x) ) {
r = mid; // (5)
}else {
l = mid; // (6)
}
}
return r; // (7)
}