【算法集训】基础算法：二分查找

这篇具有很好参考价值的文章主要介绍了【算法集训】基础算法：二分查找 | 概念篇。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二分枚举，也叫二分查找，指的就是给定一个区间，每次选择区间的中点，并且判断区间中点是否满足某个条件，从而选择左区间继续求解还是右区间继续求解，直到区间长度不能再切分为止。
由于每次都是把区间折半，又叫折半查找，时间复杂度为 O(logn)，和线性枚举的求解结果一直，但是高效许多，返回值可以是下标，也可以是元素本身。

【例题3】只有两种颜色的数组 arr ，左边部分为红色用 0 表示，右边部分为绿色用 1 表示，要求找到下标最小的绿色元素的下标。

【算法集训】基础算法：二分查找 | 概念篇,【算法集训】基础算法,算法,算法
如图所示，下标最小的绿色元素的下标为 3，所以应该返回 3。

算法分析

1）目标

对于这个问题，当我们拿到这个数组的时候，第一个绿色位置在哪里，我们是不知道的，所以，现在的目标就是要通过二分枚举找到红色区域和绿色区域的边界。

2）游标

利用线性枚举的思路，我们引入游标的概念，只不过需要两个游标，左边一个红色游标，右边一个绿色游标。并且游标初始位置都在数组以外，对于一个 n 个元素的数组，红色游标初始位置在 -1，绿色游标初始位置在 n。
【算法集训】基础算法：二分查找 | 概念篇,【算法集训】基础算法,算法,算法

3）二分

我们将两个游标相加，并且除 2，从而得到游标的中点，并且判断中点所在位置的颜色，发现是绿色的，这说明从中点游标到绿色游标的元素都是绿色的。如下图所示：
【算法集训】基础算法：二分查找 | 概念篇,【算法集训】基础算法,算法,算法
于是，我们可以把绿色游标替换成中点游标，如下图所示：

这样就完成了一次二分，区间相比之前，缩小了一半。注意，我们要求的解，一定永远在红色游标和绿色游标之间。
然后，我们继续将两个游标相加，并且除 2，从而得到游标的中点，并且判断中点所在位置的颜色，发现是红色的，这说明从红色游标到中点游标的元素都是红色的。如下图所示：
【算法集训】基础算法：二分查找 | 概念篇,【算法集训】基础算法,算法,算法
于是，我们可以把红色游标替换成中点游标，如下图所示：

同样上述算法，再经过两次二分以后，我们得到了如下结果：

这个时候，这个时候红色游标和绿色游标的位置一定相差 1，并且绿色游标的位置就是我们这个问题要求的解。文章来源地址https://www.toymoban.com/news/detail-847943.html

二分查找模版

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)
}