木鸟杂记

分布式系统，数据库，存储

数据结构与算法（二）：二分搜索

发表于 更新于 分类于

概述

以前对二分查找的认识只停留在有序数组查找给定整数上，后来发现一类问题都可以用二分的思想来做，概括来说就是：如果要求的结果所在的集合（值域）和要搜索的数的集合（定义域）存在单调（映射）关系，就可以通过二分思想来解决，说起来有点抽象，后面将用几个例子来说明。

二分思想以其每次迭代将规模砍一半的效率，有着极其广阔的应用。

本文分两大部分，第一部分对二分查找的各个细节探讨；第二部分拓展二分查找为一般的二分思想。

作者：木鸟杂记 https://www.qtmuniao.com, 转载请注明出处

二分查找–边边角角

基本代码（C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int find(vector<int> &arr, int target) {
    int left = 0, right = arr.size()-1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target){
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

像上面这一段平平无奇的代码，在实际运用的时候却又诸多变化。二分查找的基本思路不再多说，现在只分析边边角角（Corner Case）。这就涉及到我们一个基本原则，既要让所有元素有可以搜索到的机会，又不至于陷入死循环。具体来说有以下几个问题：

  1. 循环条件。什么时候用left <= right，什么时候用left < right呢？
  2. 取中方式。mid常用的有几种计算方式：mid = (left+right)/2， mid = left+(right-left)/2 和 mid = (left+right+1)/2。
  3. 边界移动。left 和 right 都有两种移动方式，拿left来说：left=mid+1 和 left=mid。
  4. 最终状态。如果没有查找到指定值，比如说[1,2,3,5]中查找数字4，那么最后跳出循环后，left 和 right 分别指向5和3的位置。也就是说，在4应该插入的位置两侧，并且left > right。

上面的几个问题其实是相互勾连的，视遇到的问题来适当组合。比如说，查找一个有序数组{1, 2, 3, 3, 3, 5}某个数字 {3} 的左右边界下标：[2, 4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int find_range(vector<int> &arr, int target, bool left_range) {
    int left = 0, right = arr.size() - 1;
    
    while (left < right) {
        int mid = left_range ? (left + right) / 2 : (left + right + 1) / 2;
        if (arr[mid] == target) {
        // Find left boundary: if we round right when calculate mid, then
        // we will trap into infinite loop here(imagine
        // we only have two elements in the array).
        // Find right boundary: the similar reason.
            left_range ? right = mid : left = mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return left;
}

上面的代码，在要查找的数字存在的时候是对的，如果不存在需要加额外判断。需要加什么判断呢？这也就是需要说明的另一个地方：当我们进行二分查找的时候，是在中途找到结果就退出(return)呢，还是一直到循环条件被打破退出呢？前者用来最简单的查找指定值，而后者一般是查找某个边界，或者符合条件的最值。该问题因为是由于破坏了循环条件left < right退出的，所以得判断下arr[left]是否和target相等。

因此：

  1. 循环条件，和移动方式和跳出边界时判断相关。

  2. 取中方式，和是否会溢出相关。比如 left 和 right 都很大，则 (left + right)/2 一般。

  3. 边界移动，这个要看是否需要循环最后跳出的左右边界结果，还是仅仅缩小范围。

  4. 最终状态，看是要查找到某个特定值结束，还是需要不断二分直到边界缩小为负值跳出。

推广二分

仔细思考有序数组的二分查找的过程可以得到几个特点：

  1. 数组数值（查找范围）和其下标（查找目标）呈现一种单调的映射关系。
  2. 每次二分，都会砍掉当前数据规模的一半，因此也叫“折半查找”。

单调映射

将二分思想推广，只要查找范围中的数值和目标值所构成的函数是单调的，我们就可以通过比较查找对象，来缩小目标值的范围。

小结

有些点还没想清楚，以后再补充。

​

我是青藤木鸟，一个喜欢摄影、专注大规模数据系统的程序员，欢迎关注我的公众号：“木鸟杂记”，有更多的分布式系统、存储和数据库相关的文章，欢迎关注。 关注公众号后，回复“资料”可以获取我总结一份分布式数据库学习资料。 回复“优惠券”可以获取我的大规模数据系统付费专栏《系统日知录》的八折优惠券。

我们还有相关的分布式系统和数据库的群，可以添加我的微信号：qtmuniao，我拉你入群。加我时记得备注：“分布式系统群”。 另外，如果你不想加群，还有一个分布式系统和数据库的论坛（点这里），欢迎来玩耍。

wx-distributed-system-s.jpg

不妨一读