# 二分搜索简介

二分法是计算机领域的经典算法,它主要用于在有序数据中搜索目标数据。由于其具有优秀的时间复杂度和相对简单的实现,因此成为了考察计算机专业学子的经典问题。

虽然二分法相比于其他算法的实现而言非常简单,但是在具体的实现过程中却又经常碰到这些让人头疼的问题:如何确定初始的下标边界范围?如何确定循环的终止条件?搜索过程中如何更新下标?

不用怀疑自己,即使是编程的大佬们也会对这个问题犯难。按照高德纳的说法[1],尽管最早的二分算法论文在 1946 年即已发表,但是第一个没有错误的二分搜索程序却直到 1962 年才出现。《编程珠玑》第 4 章中作者也提到[2],他给专业程序员布置过这个题目,在给定充足时间的条件下,至少 90% 的程序员所写的代码出现了错误。可见,这个问题并没有想象得那么简单。

# 二分法的写法探究

# 编程珠玑

既然抱着学习的心态,我们不妨先看看大佬们是如何编写二分搜索的代码的。《编程珠玑》第 5 章中,作者给出了 C 语言版本的代码,我以 C++ 将其改写如下:

template<typename T>
int binary_search(vector<T> &arr, T val)
{
    int lower = 0, upper = arr.size() - 1, mid;
    while (lower <= upper) {
        mid = (lower + upper) / 2;  // overflow
        if (arr[mid] < val) {
            lower = mid + 1;
        } else if (arr[mid] == val) {
            return mid;
        } else { /* arr[mid] > val */
            upper = mid - 1;
        }
    }
    return -1;
}

上述代码其实存在一个问题,即 mid = (lower + upper) / 2; 可能存在整数溢出的问题。这点在当时可能不是问题,因为当时的机器应该不支持 2312^31 级别的元素数量。无论如何,这样的风险总是存在的。因此这句代码现在一般都写成 mid = lower + (upper - lower) / 2;

以上的写法算是经典的选择闭区间的写法,其起始端点选择的是 [lower,upper][lower, upper] 的左闭右闭的形式,其中 NN 表示数组中的元素个数。那么常见语言的标准库中是否也是这么写的呢?

# C++ 标准库

C++ 标准库中尽管有着同名的 binary_search 函数,但它返回的其实是一个布尔值,没有给出目标值的下标。实际上的二分搜索算法应该是 lower_bound 。另一个很相似的 upper_bound 则在写法上稍有差异。我们先重点关注 lower_bound 算法。下面的算法是我改写的简易版本,标准库中使用的是迭代器的通用写法,这里为了方便理解,改写成了对数组的通用写法。

template<typename T>
int lower_bound(vector<T> arr, T val)
{
    int lower = 0;
    int upper = arr.size();
    while (lower < upper) {
        // avoid overflow
        int mid = lower + (upper - lower) / 2;
        if (arr[mid] < val) {
            lower = mid + 1;
        } else {
            upper = mid;
        }
    }
    return lower;
}

可以看到,标准库中的起始端点选择是 [0, N) ,也就是我们常说的左闭右开的写法。

可以看到,和上一小节的写法比较而言,这种写法起始端点的选择变成了 [lower, upper) ,循环终止条件由 lower <= upper 变成了 lower < upper ,区间端点值的修改上也不同。那么这种差异的原因何在呢?

其实端倪在于这个函数的名称 lower_bound 。按照说明,该函数返回的位置是第一个能够插入 val不改变数组有序性的位置。当数组中存在我们的目标值 val 的时候,那么它返回的便是数组中第一个 val 的下标位置。而如果数组中本身就不存在 val ,那么最终返回的就是 N ,即数组最后一个元素之后的位置。实际上的库函数所返回就是容器的 end() 函数返回的迭代器,这也是 C++ 库函数的一贯做法。

可以看到,这两种写法的不同之处的由来,在于他们一开始的设计思路的不同。很明显地, lower_bound 返回的总是第一个 val 值所在的位置,而 binary_search 则不能保证这一点,因此, lower_bound 函数显然更通用一点。

# 关键点分析

在编写二分搜索算法的过程中,最关键的就是以下三个问题:

  • 如何确定初始的下标边界范围?
  • 如何确定循环的终止条件?
  • 搜索过程中如何更新下标?

我们一个个来看这些问题。

# 下标初始值

那么,以上是否说明左闭右开的写法就是最优的呢?且慢,这一点并不能保证。其实本质上,所谓的闭区间和开区间其实是相对数组的下标而言的。因为实际上的返回值下标,对于数组而言可能并不合法,因此产生了开区间和闭区间的说法。所以,开闭区间说法的针对对象其实是数组本身。

我们不妨换一个角度,从返回值的下标范围来看。

对于 lower_bound 函数,其可能的返回值是 [0, arr.size()] ,恰好和一开始的 lowerupper 两个值对应。

对于 binary_search 函数,其可能的返回值是 [-1, arr.size() - 1] 。乍一看来,好像和 lower 以及 upper 的初始值并不对应。其实也可以改写成以下形式:

template<typename T>
int binary_search(vector<T> &arr, T val)
{
    int lower = -1, upper = arr.size() - 1;
    while (lower < upper) {
        int mid = upper - (upper - lower) / 2;  // overflow
        if (arr[mid] > val) {
            upper = mid - 1;
        } else { /* arr[mid] > val */
            lower = mid;
        }
    }
    return lower; // or return upper;
}

如此一来,可以发现,函数的返回值范围就能和 lowerupper 的初始值对应上了。之所以 mid 的计算改写成 upper - (upper - lower) / 2 ,是因为这样才能使 mid 的值在数组长度为 11 时合法。这种写法和上文的 lower_bound 其实是镜像对称的:将 lower 换成 upper ,并将 + 替换成 -

最终我们可以看到,对于返回值而言,并没有什么开区间和闭区间的说法,初始的设定值即表示了最终的返回值范围。而对于数组,由于存在 1-1 或者 arr.size() 的特殊下标,因此对于数组而言存在开区间和闭区间的说法。

综上,如果我们从函数返回值的角度而言,有的只是下标的取值范围。而一旦我们确定了函数的返回值范围,那么自然而然地就能够知道 lowerupper 的初始值应该如何选取了。就像上面的例子,如果使用 arr.size() 表示不存在的情况,那么 int lower = 0, upper = arr.size(); ;如果使用 1-1 表示不存在的情况,那么 int lower = -1, upper = arr.size() - 1; 。综上,我们就统一了 lowerupper 初始值的设定标准。

# 循环终止条件

在初始值确定之后,如何确定循环的终止条件呢。对于二分搜索而言,循环终止条件只有 lower <= upperlower < upper 这两种。其实这两种方法都有各自的适用情形。

  • 如果写成 lower <= upper ?下标值的初始值对于待查找数组而言必须都是合法的,即 int lower = 0, upper = arr.size() - 1; 这种形式;
  • 如果写成 lower < upper ,那么最后可能还需要对 lower 或者 upper 值做出判断。

其实我个人认为,写成 lower < upper 更好。因为这样最终循环终止时,必然是 left == right 的情形,无论返回 left 或者 right 皆可。并且如果有后续处理的需要,那么也不用纠结选择 left 还是 right 。当然,前提是选择好合适的 lowerupper 的初始值。如果像上小节中选择 lower = -1; ,还需要注意变换 mid 的计算方式,和通常的情况差别较大。

综上,推荐写成 lower < upper 。并且 lower = 0;upper 则根据需要选择合适的值。比如如果需要表明目标值不存在的特殊情况,那么推荐 upper = arr.size(); ;如果确定值一定存在,那么推荐 upper = arr.size() - 1; 。 这样一来,最后直接返回 lower (或者 upper )即可,后续的函数再根据返回值确定是否找到了对应的目标值的下标,代码也能够更简洁。

# 更新边界

边界的更新,则是一个相对复杂的问题,需要根据具体的条件来确定。一个总的原则就是,根据 mid 指示的下标是否在后续的搜索范围之内进行判断,根据初始值的设定有所不同。

如果选择 upper = arr.size(); ,那么:

if (arr[mid] < val) {
    lower = mid + 1;
} else if (arr[mid] > val) {
    upper = mid;
} else {
    return mid;
}

lower 更新为 mid + 1 很好理解,如果 mid 不符合条件,那么应该排除它。那 upper 为什么设置为 mid 呢?这时因为在 upper 的这种值初始设定下, upper 表示的下标要么对于数组不合法,要么不在后续的搜索范围之内。通过判断, mid 不在后续搜索的范围之内,那么 upper 就应该设置为 mid 。如果设置为 mid - 1 ,表示的意义则是 mid - 1 不在搜索范围之内,显然和我们的意思相违背。

类似地,如果选择 upper = arr.size() - 1; ,那么:

if (arr[mid] < val) {
    lower = mid + 1;
} else if (arr[mid] > val) {
    upper = mid - 1;
} else {
    return mid;
}

lower 更新为 mid + 1 很好理解,如果 mid 不符合条件,那么应该排除它。此时 upper 的初始值下标对于数组也是合法的,那么就应该设置为 mid - 1 ,表示的意义则是 mid - 1 在后续的搜索范围之内。

此外,上述两端代码写成三个判断条件是为了方便比较它们的异同。在具体的题目中,可以简化成上文的类似 lower_bound 的形式,在最后统一返回最终的下标值。

综上而言, upper 的更新需要根据其初始值的设定及具体情况来确定。

# LeetCode 例题

LeetCode 162 中一定存在有效解,所以这一题最好的选择就是 upper = arr.size() - 1

选择 upper = arr.size() ,统一表示不存在的情形。如果和题目规定的异常返回值不一致,那么后续再判断修改即可。典型的题目有 LeetCode 33LeetCode 34LeetCode 35

其他参考资料,可以参考知乎回答[3] labuladong 的解析[4]


  1. The Art of Computer Programming Volume 3: Sorting and Searching 第 6.2.1 节 ↩︎

  2. 编程珠玑 第 4 章,第 5 章 ↩︎

  3. 知乎:二分查找有几种写法?它们的区别是什么? ↩︎

  4. 二分查找详解 ↩︎