简明现代魔法 -> 计算机算法 -> 只有1/10的程序员能正确实现二分查找

只有1/10的程序员能正确实现二分查找

2011-02-12

有一些讲编程的图书,我会从头到尾、一字不落地反复研读;还有一些讲编程的图书,我已经看过好几遍了,但每次差不多都是只看其中的一章。乔恩·本特利(Jon Bentley)1986年的经典名著《编程珠玑》(Programming Pearls)则是少数几本能同时归入上述两类的编程图书之一。

我打算最近再专门写一篇关于这本书的文章,但今天我只想就这本书中的几段话谈谈自己的想法。这几段内容有点骇人听闻。

只有10%的程序员可以写出二分查找

每次翻开《编程珠玑》,我都会先看一看下面这几段文字:

二分查找可以解决(预排序数组的查找)问题:只要数组中包含T(即要查找的值),那么通过不断缩小包含T的范围,最终就可以找到它。一开始,范围覆盖整个数组。将数组的中间项与T进行比较,可以排除一半元素,范围缩小一半。就这样反复比较,反复缩小范围,最终就会在数组中找到T,或者确定原以为T所在的范围实际为空。对于包含N个元素的表,整个查找过程大约要经过log(2)N次比较。

多数程序员都觉得只要理解了上面的描述,写出代码就不难了;但事实并非如此。如果你不认同这一点,最好的办法就是放下书本,自己动手写一写。试试吧。

我在贝尔实验室和IBM的时候都出过这道考题。那些专业的程序员有几个小时的时间,可以用他们选择的语言把上面的描述写出来;写出高级伪代码也可以。考试结束后,差不多所有程序员都认为自己写出了正确的程序。于是,我们花了半个钟头来看他们编写的代码经过测试用例验证的结果。几次课,一百多人的结果相差无几:90%的程序员写的程序中有bug(我并不认为没有bug的代码就正确)。

我很惊讶:在足够的时间内,只有大约10%的专业程序员可以把这个小程序写对。但写不对这个小程序的还不止这些人:高德纳在《计算机程序设计的艺术 第3卷排序和查找》第6.2.1节的"历史与参考文献"部分指出,虽然早在1946年就有人将二分查找的方法公诸于世,但直到1962年才有人写出没有bug的二分查找程序。

——乔恩·本特利,《编程珠玑(第1版)》第35-36页

几个小时!90%!老兄,严肃点!难道这还不够骇人听闻吗?

之所以想看这本书的第2版,原因之一就是想看看这几段文字有没有修订过,看看从1986年到1999年出第2版,这个数字有没有变化。直觉告诉我,这个数字一定向好的方向变化了,事物都是向好的方向发展的嘛。但理性却告诉我,在一个程序员把更多的时间都花在摆弄库上,而不是编写实际代码的时代,重现核心算法的能力即使有也一定会弱化。别忘了,本特利提到的那些家伙可都不是等闲之辈,他们都是贝尔实验室和IBM的专业人员。所以,我们有理由相信他们的成绩实际上已经是最好的了。

好,下面就做一个二分查找的测验。

我跟你一样(如果你是这么想的),想马上就试一试。(好啦,不是马上。先看完这篇文章!)我相信看这篇文章的人都知道什么是二分查找算法,即使你不知道,上面引用的本特利的描述也应该够了。请你打开编辑器,编写一个二分查找例程。什么时候觉得没有任何问题了,保留那个版本。然后测试,然后通过在下面留言的方式告诉我你是不是第一次就做对了。我们肯定能打破本特利10%的纪录吗?

规则如下:

  1. 使用你喜欢的任何编程语言。
  2. 不要剪切粘贴或以任何方式复制别人的代码。甚至在你写完之前,都不要参考其他的二分查找代码。
  3. 甚至于我不得不强调,别调用bsearch(),或使用其他瞒天过海的手法
  4. 时间自己来定:5分钟不短——只要你能保证写完写对;8小时不长——只要你愿意(而且有那么多闲工夫)。
  5. 可以使用编译器消除一些无意识的错误,如语法错误或变量初始化失败,但……
  6. 在确定程序正确之前不要测试。
  7. 最后,也是最重要的:如果决定参与这次测验,就必须报告。成功也好,失败也罢,甚至半途而废也要给我个话儿。否则,就无法保证测验结果的准确性了。

(考虑到这只是一次测验,可以忽略计算索引时导致的数值溢出。这里描述了相应的情形,但打算参加这次测验的人在编完程序之前不要看,因为那篇文章里包含一个正确的二分查找的实现,对自己能力有自信的朋友一定是不屑为之的。)

如果你的代码经验证确实正确,那么如果你愿意的话,欢迎你在留言里贴出自己的代码。不过,假如你这样做了,而后来的留言给你挑出了bug,请你一定想好怎样为维护自己的形象而自圆其说。更酷的玩法:对于那些信心十足的人,如果你真敢肯定自己的程序没有问题,可以先把代码贴在留言里,然后再测试。当然,你必须要在留言里说明这一点,以便大家发现你的bug时,会考虑多少给你留些情面。

专注前端开发的程序员们,可以参考《JavaScript高级程序设计》的作者Nicholas C. Zakas使用JavaScript实现的一些基本算法,链接地址如下http://www.nczonline.net/blog/tag/computer-science/。其中,对本文提到的二分查找算法的实现如下:

//Copyright 2009 Nicholas C. Zakas. All rights reserved.
//MIT-Licensed, see source file
function binarySearch(items, value){
 
    var startIndex  = 0,
        stopIndex   = items.length - 1,
        middle      = Math.floor((stopIndex + startIndex)/2);
 
    while(items[middle] != value && startIndex < stopIndex){
 
        //adjust search area(调整查找范围)
        if (value < items[middle]){
            stopIndex = middle - 1;
        } else if (value > items[middle]){
            startIndex = middle + 1;
        }
 
        //recalculate middle(重新计算中项索引)
        middle = Math.floor((stopIndex + startIndex)/2);
    }
 
    //make sure it's the right value(确保返回正确的值)
    return (items[middle] != value) ? -1 : middle;
}
随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们