你会写二分查找吗？

你是10%能够写对二分查找的程序员之一吗？

这篇文章：

http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/ （原文）

http://news.csdn.net/a/20100423/218099.html （译文）

给我们一个有趣的结论：只有10%程序员能正确实现二分查找算法。

乔恩·本特利编写的《编程珠玑》中有这样的话：

一开始，范围覆盖整个数组。将数组的中间项与T进行比较，可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。……多数程序员都觉得只要理解了上面的描述，写出代码就不难了；但事实并非如此。……一百多人的结果相差无几：90%的程序员写的程序中有bug（我并不认为没有bug的代码就正确）。

10%？多么惊人的数字，事实真的如此么？迈克·泰勒（Mike Taylor）在他那篇文章的评论中重复了这个实验：（翻译+注解）

请你打开编辑器，编写一个二分查找例程。什么时候觉得没有任何问题了，保留那个版本。然后测试，然后通过在下面留言的方式告诉我你是不是第一次就做对了。我们肯定能打破本特利10%的纪录吗？

规则如下。

1.使用你喜欢的任何编程语言。（事实上回复的人用到了至少20种语言，还有各种伪代码）

2.不要剪切粘贴或以任何方式复制别人的代码。甚至在你写完之前，都不要参考其他的二分查找代码。

3.甚至于我不得不强调，别调用bsearch()，或使用其他瞒天过海的手法（这个是必须得）

4.时间自己来定：5分钟不短——只要你能保证写完写对；8小时不长——只要你愿意（而且有那么多闲工夫）。（写二分查找需要多久？我曾经考试的时候一个小时没写出来）

5.可以使用编译器消除一些无意识的错误，如语法错误或变量初始化失败，但……（有些IDE是很强大的）

6.在确定程序正确之前不要测试。（一次写成）

7.最后，也是最重要的：如果决定参与这次测验，就必须报告。成功也好，失败也罢，甚至半途而废也要给我个话儿。否则，就无法保证测验结果的准确性了。（这个比较重要）

 

结果如何呢？博主没有进行明确的统计，但翻看代码我们不难发现许多问题，例如这个：

class Array
  def bsearch(n, from = 0, to = self.length)
    middle = from + ((to - from) / 2)
    value = self[middle]
    if value == n
      return middle
    elsif value < n
      return bsearch(n, middle, to)
    else
      return bsearch(n, from, middle)
    end
  end
end

arr = [1,2,3,4,5,6,7,8,9,10]

arr.each do |search|
  index = arr.bsearch(search)
  puts "search(#{search}) => #{index}, #{arr[index]}"
end

far from perfect. 15 minutes. doesn’t work when item is not in array (stack overflow)

程序不完美，15分钟，当数组中不存在所求元素是会堆栈溢出

 

我不知道这是什么语言编写的（Morenan神牛认出是Ruby，orz），但错误比较显然，如果arr[from..to]=[1,2]，在其中二分查找2（满足元素在数组中能找到），这个程序将堆栈溢出（因为bsearch(2,1,2)判断a[1]<2成立会调用bsearch(2,1,2)，程序将无限递归下去直到溢出）。

还有更多错误，有兴趣的同学可以自己去找。

高德纳在《计算机程序设计的艺术 第3卷 排序和查找》第6.2.1节的“历史与参考文献”部分指出：虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序。

可见二分查找原理简单，实现起来却不容易，那么，有没有正确而通用的算法呢？

在这里，我提出一种方法（你也可以思考出自己的方法）。然后，背过它，要相信这比用到的时候再想靠谱的多：

先考虑一种“简单”的情况：

数组a满足a[1]=a[2]=a[3]=…=a[k-1]=0，a[k]=a[k+1]=a[k+2]=…=a[n]=1，求1第一次出现的位置（或0最后一次出现的位置）。

function binarySearch1:longint;
  var
    l,r,mid:longint;
  begin
    a[0]:=0; a[n+1]:=1;
    l:=0; r:=n+1;
    while l<r do
    begin
      mid:=(l+r) div 2;
      if a[mid]=0 then
        l:=mid+1
      else
        r:=mid;
    end;
    exit(l);
  end;

binarySearch1将返回a数组中1第一次出现的位置。

那么，如何求0最后一次出现的位置呢？很简单：

function binarySearch0:longint;

  begin exit(binarySearch1-1); end;

binarySearch将0返回a数组中0最后一次出现的位置。

也许你认为这个算法通用性不高，但事实上不是这样。

考虑这样一个问题：在一个已排序的可能有重复元素的数组a中，二分查找元素data第一次（最后一次）出现的位置（data保证在数组a中出现过）。

如果我们定义数组b满足：

b[i] = 0 if a[i]<data
b[i] = 1 if a[i]>=data

则b数组的binarySearch1即为a数组中data第一次出现的位置，b数组的binarySearch0即为a数组中data最后一次出现的位置。

可以证明，这个算法是正确的：data第一次出现的位置必然是数组a中大于等于data的元素开始的位置；data最后一次出现的位置必然是数组a中大于data的元素开始的位置减一。

 

二分不止局限于二分查找，在二分答案法中应用也很广。

当二分枚举答案时，判断当前枚举的答案（k）是否可行，若可行，则记a[k]=1（或0），若不可行，则记a[k]=0（或1）。这样，又转变成了最简单的情况，binarySearch0和binarySearch1即为临界点。

对于所有的二分，都可以转化成求1（或0）第一次（或最后一次）出现的位置的问题。例如求未在数组a中出现过的元素data满足a[k-1]<data<a[k]的位置k，就可以定义a[i]>data为1，a[i]<data为0，求出binarySearch1即可。

Ps：在实际应用中，不必求出存储01的数组b，只许要将 if a[mid]=0 then 改为满足 b[i]=0 的条件即可。

 

2010年10月28日第一版

2015年12月10日重新校对