技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置：首页 --> 奋斗 --> 你是那10%可以实现二分查找算法的程序员吗？

你是那10%可以实现二分查找算法的程序员吗？

浏览:6510次  出处信息

原文链接：http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/
迈克・泰勒（Mike Taylor），2010年4月19日
翻译完成：2010年4月20日

有一些讲编程的图书，我会从头到尾、一字不落地反复研读；还有一些讲编程的图书，我已经看过好几遍了，但每次差不多都是只看其中的一章。乔恩・本特利（Jon Bentley）1986年的经典名著《编程珠玑》（Programming Pearls）则是少数几本能同时归入上述两类的编程图书之一，我手里这本书的封面已经严重磨损，下图可以为证（点击看大图，注意左下角。――译者注）。

（我有这本书的第1版[amazon.com，amazon.co.uk]，上面就是扫描的这一版的封面，好像我该买一本又新又便宜的第2版了[amazon.com，amazon.co.uk]，第2版比第1版多了3章内容。）

我打算最近再专门写一篇关于这本书的文章（我已经为Coders at Work、The Elements of Programming Style、Programming the Commodore 64 和The C Programming Language专门写了几篇书评），但今天我只想就这本书中的几段话谈谈自己的想法。这几段内容有点骇人听闻。

只有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时，会考虑多少给你留些情面。

我会在某个时间总结一下这次测试的结果――比如说，一周以后。

行动吧！

第一次更新（一个半小时后）

感谢朋友们的积极响应，这么快就有那么多留言！我得提醒大家，WordPress的留言系统会解释HTML，因此会吞掉类似下面的代码段

if a[mid] < value

最好的办法就是把源代码放在{source}…{source}标签之间，注意用方括号代替这里的花括号。（我第一次想告诉大家这一点时，使用的是方括号，结果我写的规避标记的说明，反而被当成了标记――悲哀呀！）这样做还可以保留缩进，否则我还不知道有什么办法可以做到这一点。

替WordPress向大家致歉：我真的希望这个平台允许留言者预览留言和/或在发表后还能编辑留言，这样就可以避免出现乱七八糟的代码了。我也想了办法自己动手解决这个问题，但WordPress不仅会错误地显示带有<符号的代码，它实际上会丢弃该符号后面的所有内容，唉，我想我是没折了。

第二次更新（在原文章发表4个小时后）

哈哈，你们这些家伙太出人意料了。仅仅4个小时，这篇文章的留言数就超过了以前的一篇文章保持的纪录（Whatever Happened to Programming此时的留言有206条）。

如果想看到相关的更多讨论，Hacker News中有不少不错的留言，另外Reddit的留言质量虽然差一点，但也值得一看。这些讨论把实际地编写代码看成只有精英程序员才会干的事。

译后记：看了几眼，能认出来的加上认不出来的：C、PHP、Ruby、Python、Common Lisp、VB.NET 、C#、Java、Javascript、Delphi、Haskell、Scheme、Clojure、Perl、Smalltalk、FORTRAN、Lua、Objective-C、ColdFusion……各种各样语言的实现齐聚一堂。

有心人乔尔・甘勒（Joe Ganley）对前100个留言作了统计，结果如下：

Python 40
C/C++ 36
Unknown/pseudocode 6
Lisp/Clojure/Scheme 5
PHP 4
Three each: Java, Perl, C#, JavaScript
Haskell 2
One each: VB, Delphi, Smalltalk, FORTRAN, Lua, Objective-C, ColdFusion

Conclusion: Almost everyone (who cares about implementing binary search, anyway) uses C/C++ or Python.

PS：专注前端开发的程序员们，可以参考《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;
}

建议继续学习：

  1. 腾讯-1亿个数据取前1万大的整数-题解答    (阅读：9047)
  2. 谷歌(Google)2011年校园招聘笔试题    (阅读：8913)
  3. 15道使用频率极高的基础算法题    (阅读：5625)
  4. 更快的IP库查找方法以及AWK中的二分查找    (阅读：5250)
  5. 新浪微博笔试题：找出共有2个以上标签的用户对    (阅读：4974)
  6. 有道实习生笔试总结    (阅读：4542)
  7. 2014网易前端开发笔试题笔记    (阅读：3952)
  8. 《百姓网公开笔试题：查询条件的子集判断》的一份 PHP 答卷    (阅读：2738)
  9. 百姓网公开笔试题：查询条件的子集判断    (阅读：2576)
  10. 百姓网公开笔试题结果展示    (阅读：2316)
QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习
<< 前一篇：Nicholas C. Zakas谈怎样才能成为优秀的前端工程师
后一篇：RedHat 相关证书过期时间与 RHCE 认证新的变更 >>
文章信息
© 2009 - 2024 by blogread.cn 微博：@IT技术博客大学习

京ICP备15002552号-1