编程珠玑-错误的二分查找算法（中）

微信公众号：科文路。转发须注明出处。

源自《编程珠玑》第 2 版第 5 章，《编程小事》

（上）部分主要介绍二分查找算法原理以及一些编程理念，（中）讲解测试方法，并揪出错误，（下）部分通过运行时间分析来验证算法时间复杂度。

本文较长，但值得细读、学习、思考。

本文成文仓促，后续若有修正，将在文末阅读原文的博客文章上进行。

在上一篇文章编程珠玑-错误的二分查找算法（上），已经

• 将元素查找的问题转化为了程序设计问题，
• 确定了二分查找算法的完成方式并相应地确定了数据类型，
• 最终设计出了一个 Python 函数，

而且这个程序在样例数据上表现正确无误。

这篇文章的标题已经说了，这个查找算法是错误的。所以本文通过建立一系列通用的测试代码（在《编程珠玑》中被称为脚手架（scaffolding）），来探察、测试代码，并且通过了解其运行时间来测算时间复杂度。

请注意，本文的代码以不含过多技巧的 Python 编写，意在能确实执行的同时表示伪代码。

回归正题，先看三个二分查找算法中的第一个。

第一段代码

def binary_search_e1(arr, t):
    l, r = 0, len(arr) - 1
    while l <= r:
        m = (l + r) // 2  # 取整
        print("  current l: %d, m: %d, r: %d" % (l, m, r))
        if arr[m] < t:
            l = m   # 将搜索范围调整为 m 右侧
        elif arr[m] > t:
            r = m   # 将搜索范围调整为 m 左侧
        else:
            return m    # 找到
    return -1   # 没有找到

程序看起来没有什么问题。接下来写一个脚手架，进行一些简单的测试。

往往在做简单的测试的时候，使用 print 打印当前的变量值比 debug 工具单步调试方便的多。比如这段程序的第 5 行打印当前的被查找区间的左端索引、待查值、被查找区间的右端索引。

# 一个脚手架做简单测试
while True:
    # 被查数组
    arr = []
    n, t = map(int, input().split())    # no assertion for inputs
    if -1 == n:
        break
    for i in range(n):
        arr.append(10 * i)
    print("binary_search_e1: %d\n" % (binary_search_e1(arr, t)))

这种方式的测试主要意在验证程序是否能通过编译、正常跑起来，并试图检测一些简单的错误。

接下来在脚手架程序上输入测试用例，

$ python binary_search_test.py
5 20
  current l: 0, m: 2, r: 4
binary_search_e1: 2

5 30
  current l: 0, m: 2, r: 4
  current l: 2, m: 3, r: 4
binary_search_e1: 3

5 40
  current l: 0, m: 2, r: 4
  current l: 2, m: 3, r: 4
  current l: 3, m: 3, r: 4
  current l: 3, m: 3, r: 4
  ...
  ...

发现在输入 5 40 时，程序进入了死循环。在本例中，由于区间边界的计算逻辑错误导致 l <= r 在上述情况下无法达到。经过对边界条件设置的摸索后，改成了第二段代码的形式。

第二段代码

def binary_search_e2(arr, t):
    l, r = 0, len(arr) - 1
    while l <= r:
        m = round((l + r) / 2)  # 取整
        # print("  current l: %d, m: %d, r: %d" % (l, m, r))
        if arr[m] < t:
            l = m + 1   # 将搜索范围调整为 m 右侧
        elif arr[m] > t:
            r = m - 1   # 将搜索范围调整为 m 左侧
        else:
            return m    # 找到
    return -1   # 没有找到

再运行上述的脚手架，程序运行正常了。但路过的小杨觉得这还不够，还需要在更多的测试数据上运行，确保程序正确。于是引入了自动测试。

自动测试

为了完成自动测试，务必了解 assert。

断言：assert

在程序中插入 assert，可以确保程序与编码人的理解一致。断言简化了设计条件语句来 debug 程序的流程。其仅在目标语句为 false 时，中断程序、抛出 error。

例如，

assert(0 > 1)

将会抛出

>>> assert(0 > 1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError

又如本文，应确保待查询的数组是严格有序的，可以使用如下 assert，

def sorted(arr):
    for i in range(len(arr)-1):
        if arr[i+1] < arr[i]:
            return False
        return True

assert(sorted())

然后一个自动测试的脚手架被设计成下面这样。

自动测试的脚手架

arr = []
MAX_N = int(input("Input maximum length for the array: "))
for i in range(MAX_N):
    arr.append(10 * i)
for i in range(MAX_N):
    assert(binary_search_right(arr, i * 10) == i)
    assert(binary_search_right(arr, i * 10 - 5) == -1)
assert(binary_search_right(arr, 10 * MAX_N - 5) == -1)
assert(binary_search_right(arr, 10 * MAX_N) == -1)

运行这个脚手架，

$ python binary_search_autotest.py
Input maximum length for the array: 100
$ python binary_search_autotest.py
Input maximum length for the array: 1000
$ python binary_search_autotest.py
Input maximum length for the array: 100000

没有抛出 error，说明程序运行一切正确。

C++ 代码

小杨非常开心，拿过 binary_search_e2 就改写成了 C++ 代码，

#include <cassert>
#include <iostream>
#include <vector>

int binary_search_e2(const std::vector<long> &arr, long t) {
  int l = 0;
  int r = arr.size();

  while (l <= r) {
    int m = （l + r) / 2;
    if (arr[m] < t) {
      l = m + 1;
    } else if (arr[m] > t) {
      r = m - 1;
    } else {
      return m;
    }
  }
  return -1;
}

int main() {
  int MAX_N;
  std::cout << "MAX_N: ";
  std::cin >> MAX_N;

  std::vector<long> arr;
  for (long i = 0; i < MAX_N; ++i) {
    arr.push_back(10 * i);
  }
//   std::cout << "arr[MAX_N], " << arr.back() << "; arr.size, " << arr.size()
//             << std::endl;

  for (auto i = 0; i < MAX_N; ++i) {
    assert(binary_search_e2(arr, i * 10) == i);
    assert(binary_search_e2(arr, i * 10 - 5) == -1);
  }
}

测试一下，

$ g++ binary_search.cpp -o binary_search
$ ./binary_search
$ MAX_N: 1000
$ ./binary_search
$ MAX_N: 1000000
$ ./binary_search
$ MAX_N: 1200000000
Segmentation fault (core dumped)

当输入的 MAX_N 为 1200000000 时，程序报错了。

第二段代码的错误分析

1200000000 的取值的意思是大于 INT_MAX（2147483647）的一半

通过细心的分析，最终，发现错误出在 m = (l + r) / 2 导致了溢出。当输入大于 INT_MAX 的一半时，求和的结果不再是正确的 int 值。而原来由于 Python 的特殊数据类型机制，导致 Python 中的计算，不会出现溢出。

好了，写了这么多，就是想说问题就出在 m = (l + r) / 2。于是将其改成 m = l + (r - l) / 2， 或者 m = l + ((r - l) >> 1)，确保不溢出。

再编译、运行，成功通过上述不成功的用例。

第三段代码

终于，一个看起来没有错误的二分查找算法完成了。

def binary_search_right(arr, t):
    l, r = 0, len(arr) - 1
    while l <= r:
        m = l + (r - l) // 2  # 取整
        # print("  current l: %d, m: %d, r: %d" % (l, m, r))
        if arr[m] < t:
            l = m + 1   # 将搜索范围调整为 m 右侧
        elif arr[m] > t:
            r = m - 1   # 将搜索范围调整为 m 左侧
        else:
            return m    # 找到
    return -1   # 没有找到

接下来，（下）部分通过运行时间分析来验证算法时间复杂度。

在这之前，希望读者能好好体会这篇文章，领悟测试驱动改进的逻辑。

AGAIN，本文成文仓促，后续若有修正，将在下面阅读原文的博客文章上进行。