二分查找详细讲解（C 代码演示）

短命女 2022-12-25 05:00 209阅读 0赞

### 文章目录 ###

*  引言
 *  普通二分查找
 *  特殊二分查找
 *   *  000111型
     *  111000型
 *  特殊二分查找的应用——二分答案

# 引言 #

二分查找是时间复杂度为`O(logn)`的简单算法，适用于在有序的数组中查找想要的数据，这里的数组也可以换成具有单调性的函数，把函数的传入值类比成数组的下标，函数的返回值类比成数组内这个下标存储的元素，那么函数就是不用开辟额外空间存储元素的压缩数组。

--------------------

# 普通二分查找 #

假设数组中数据的值是单调递增的，定义左边界`left`和右边界`right`，从中间下标`mid =（left + right）/ 2`开始搜索目标值`target`：

1.  如果`arr[mid] == target`，返回其在数组中的下标`mid`；
2.  如果`arr[mid] > target`，说明现在的数据大了，要减小数据，则要让`right`变小，所以`right = mid - 1`；
3.  如果`arr[mid] < target`，说明现在的数据小了，要增大数据，则要让`left`变大，所以`left = mid + 1`；

每次搜索可以丢弃当前边界内一半不符合的数据，进行下一次搜索前，先更新`mid`，直到左右边界内没有数据可搜索了，或者找到目标数据，返回其在数组中的下标。

图解过程：

在数组arr = \{1,2,3,4,5,6,7,8,9\} 中，找到target = 6

![00][]

代码实现如下：

int binary_search(int *arr, int left, int right, int target)
    {
        
        int mid = 0;
        while (left <= right)
        {
        
            mid = (left + right) / 2;
            if (arr[mid] == target)
            {
        
                return mid;
            }
            else if (arr[mid] > target)
            {
        
                right = mid - 1;
            }
            else if (arr[mid] < target)
            {
        
                left = mid + 1;
            }
        }
        return -1;//没有找到数据，返回-1。
    }

--------------------

# 特殊二分查找 #

## 000111型 ##

假设需要查找的目标`target = 1`，一个数组内存的数据为`arr = {0,0,0,1,1,1}`，要找到数组中第一个出现的target的下标，`left = 0`，`right = 5`，还是从`mid = (left + right) / 2`开始搜索：

1.  如果`arr[mid] = = target`，此时不知道找到的是第几个出现的`1`，所以这个结果要保留，现在下一次搜索从`mid`向前搜，`right = mid`；
2.  如果`arr[mid] != target`，此时这个结果不需要保留，现在下一次搜索从`mid + 1`向后搜，`left = mid + 1`；

每次搜索可以丢弃当前边界内一半的数据，进行下一次搜索前，先更新`mid`，直到左右边界重合，此时`left`或`right`即是要找的下标。

PS: 假设更极端的情况，数组为`arr = {0,0,0,0,0,0}`，没有`1`，即没有目标值。

>   二分查找搜索到最后，`left = right = 5`，但是这个下标并不是正确答案，所以此时二分查找结束后，应该做个判断，判断这个下标内的数据是不是`target`；也可以在搜索刚开始时，让`right = 6`，超过了数组上限1位，当作虚拟尾元素，二分查找结束后，判断返回的下标是否合法，即是不是`6`，是`6`则没有找到`target`，不是`6`则没找到`target`。

图解过程：

在数组arr = \{0,0,0,1,1,1,1,1,1\} 中，找到第一个1的下标。

![01][]

代码实现如下：

int binary_search_01(int *arr, int left, int right, int target)
    {
        
        int mid = 0;
        while (left != right)
        {
        
            mid = (left + right) / 2;
            if (arr[mid] == target)
            {
        
                right = mid;
            }
            else
            {
        
                left = mid + 1;
            }
        }
        return left;
    }

--------------------

## 111000型 ##

假设需要查找的目标`target = 1`，一个数组内存的数据为`arr = {1,1,1,0,0,0}`，要找到数组中最后一个出现的target的下标，`left = 0`，`right = 5`，从 mid = (left + right) / 2 开始搜索：

1.  如果`arr[mid] = = target`，此时不知道找到的是第几个出现的`1`，所以这个结果要保留，现在下一次搜索从`mid`向后搜，`left = mid`；
2.  如果`arr[mid] != target`，此时这个结果不需要保留，现在下一次搜索从`mid + 1`向前搜，`right = mid - 1`；

每次搜索可以丢弃当前边界内一半的数据，进行下一次搜索前，先更新`mid`，直到左右边界重合，此时`left`或`right`即是要找的下标。

PS:`mid = (left + right) / 2`真的合理吗？

> 假设数组为`arr = {1,0}`，`left = 0`，`right = 1`，`mid = (0 + 1) / 2 = 0`，
> 
> 则`arr[mid] == 1`，`left = mid = 0`，可以看到此时left并没有被更新，会导致死循环，正确的做法是mid = (left + right + 1) / 2

PS: 假设更极端的情况，数组为`arr = {0,0,0,0,0,0}`，没有`1`，即没有目标值。

>   用二分查找搜索到最后，`left = right = 0`，但是这个下标并不是正确答案，所以此时二分查找结束后，应该做个判断，判断这个下标内的数据是不是`target`；也可以在搜索刚开始时，让`left = -1`，超过了数组下限1位，当作虚拟头元素，二分查找结束后，判断返回的下标是否合法，即是不是`-1`，是`-1`则没有找到`target`，不是`-1`则没找到`target`。

图解过程：

在数组arr = \{1,1,1,1,1,1,0,0,0\} 中，找到最后一个1的下标。

![10][]

代码实现如下：

int binary_search_10(int *arr, int left, int right, int target)
    {
        
        int mid = 0;
        while (left != right)
        {
        
            mid = (left + right + 1) / 2;
            if (arr[mid] == target)
            {
        
                left = mid;
            }
            else
            {
        
                right = mid - 1;
            }
        }
        return left;
    }

--------------------

# 特殊二分查找的应用——二分答案 #

二分答案，顾名思义就是在所有可能答案的区间内，用二分查找搜索出目标值。说的有些抽象，下面我以leetcode278题做例子讲解一下二分答案的思路。

> [278. 第一个错误的版本][278.]
> 
> 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
> 
> 假设你有 n 个版本 \[1, 2, …, n\]，你想找出导致之后所有版本出错的第一个错误的版本。
> 
> 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
> 
> 示例:
> 
>     给定 n = 5，并且 version = 4 是第一个错误的版本。
>     
>     调用 isBadVersion(3) -> false
>     调用 isBadVersion(5) -> true
>     调用 isBadVersion(4) -> true
>     
>     所以，4 是第一个错误的版本。
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/first-bad-version  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

读题后得到的有，目前有n个版本产品，需要知道第一个出现错误的版本是哪一个。

![22][]

上图是我根据示例中的数据所画出来的解题思路，将找第一个出现错误的版本，转换为找数组中第一个1的下标，在解题过程中`isBadVersion()`函数就相当于一个数组来使用。将问题转换成特殊的二分查找后，就可以按照上面介绍的二分查找模板完成代码了，这题是属于000111型。

// The API isBadVersion is defined for you.
    // bool isBadVersion(int version);
    
    int firstBadVersion(int n) {
        
        long left = 1, right = n;
        long mid = 0;
        while (left != right) 
        {
        
            mid = (left + right) / 2;
            if (isBadVersion(mid)) 
            {
        
                right = mid;
            }
            else
            {
        
                left = mid + 1;
            }
        }
        return left;
        /*
        因为题目必定有答案，所以可以不判断能不能找到。
        if (isBadVersion(left)) {
            return left;
        }
        else
        {
            return -1;
        }
        */
    }

[00]: /images/20221120/b2fccad738cd4c7b8da2323ba336df86.png
[01]: /images/20221120/0123c2f416794195a4a9b3f7b723dfb3.png
[10]: /images/20221120/44a71542c4e24deaab194d5d6b05a483.png
[278.]: https://leetcode-cn.com/problems/first-bad-version/
[22]: https://img-blog.csdnimg.cn/20201130180434271.png#pic_center