你是那10%可以实现二分查找算法的程序员吗？
2010年04月20日 编程技术, 翻译
——《编程珠玑》引发的编程竞赛
原文链接：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的二分查找程序。
几个小时！90%！老兄，严肃点！难道这还不够骇人听闻吗？
之所以想看这本书的第2版，原因之一就是想看看这几段文字有没有修订过，看看从1986年到1999年出第2版，这个数字有没有变化。直觉告诉我，这个数字一定向好的方向变化了，事物都是向好的方向发展的嘛。但理性却告诉我，在一个程序员把更多的时间都花在摆弄库上，而不是编写实际代码的时代，重现核心算法的能力即使有也一定会弱化。别忘了，本特利提到的那些家伙可都不是等闲之辈，他们都是贝尔实验室和IBM的专业人员。所以，我们有理由相信他们的成绩实际上已经是最好的了。
好，下面就做一个二分查找的测验
我跟你一样（如果你是这么想的），想马上就试一试。（好啦，不是马上。先看完这篇文章！）我相信看这篇文章的人都知道什么是二分查找算法，即使你不知道，上面引用的本特利的描述也应该够了。请你打开编辑器，编写一个二分查找例程。什么时候觉得没有任何问题了，保留那个版本。然后测试，然后通过在下面留言的方式告诉我你是不是第一次就做对了。我们肯定能打破本特利10%的纪录吗？
规则如下。
- 使用你喜欢的任何编程语言。
- 不要剪切粘贴或以任何方式复制别人的代码。甚至在你写完之前，都不要参考其他的二分查找代码。
- 甚至于我不得不强调，别调用bsearch()，或使用其他瞒天过海的手法
- 时间自己来定：5分钟不短——只要你能保证写完写对；8小时不长——只要你愿意（而且有那么多闲工夫）。
- 可以使用编译器消除一些无意识的错误，如语法错误或变量初始化失败，但……
- 在确定程序正确之前不要测试。
- 最后，也是最重要的：如果决定参与这次测验，就必须报告。成功也好，失败也罢，甚至半途而废也要给我个话儿。否则，就无法保证测验结果的准确性了。
（考虑到这只是一次测验，可以忽略计算索引时导致的数值溢出。这里描述了相应的情形，但打算参加这次测验的人在编完程序之前不要看，因为那篇文章里包含一个正确的二分查找的实现，想洁身自好的朋友一定是不屑为之的。）
如果你的代码经验证确实正确，那么如果你愿意的话，欢迎你在留言里贴出自己的代码。不过，假如你这样做了，而后来的留言给你挑出了bug，请你一定想好怎样为维护自己的形象而自圆其说
更酷的玩法：对于那些信心十足的人，如果你真敢肯定自己的程序没有问题，可以先把代码贴在留言里，然后再测试。当然，你必须要在留言里说明这一点，以便大家发现你的bug时，会考虑多少给你留些情面。
我会在某个时间总结一下这次测试的结果——比如说，一周以后。
行动吧！
第一次更新（一个半小时后）
感谢朋友们的积极响应，这么快就有那么多留言！我得提醒大家，WordPress的留言系统会解释HTML，因此会吞掉类似下面的代码段
if a[mid] < value
最好的办法就是把源代码放在{source}…{source}标签之间，注意用方括号代替这里的花括号。（我第一次想告诉大家这一点时，使用的是方括号，结果我写的规避标记的说明，反而被当成了标记——悲哀呀！）这样做还可以保留缩进，否则我还不知道有什么办法可以做到这一点。
替WordPress向大家致歉：我真的希望这个平台允许留言者预览留言和/或在发表后还能编辑留言，这样就可以避免出现乱七八糟的代码了。我也想了办法自己动手解决这个问题，但WordPress不仅会错误地显示带有<符号的代码，它实际上会丢弃该符号后面的所有内容，唉，我想我是没折了。
第二次更新（在原文章发表4个小时后）
哈哈，你们这些家伙太出人意料了。仅仅4个小时，这篇文章的留言数就超过了以前的一篇文章保持的纪录（Whatever Happened to Programming此时的留言有206条）。
如果想看到相关的更多讨论，Hacker News中有不少不错的留言，另外Reddit的留言质量虽然差一点，但也值得一看。这些讨论把实际地编写代码看成只有精英程序员才会干的事。
有心人乔尔·甘勒（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;
- }
John Resig谈改进Web应用的高级JavaScript技术[待续]
2010年04月9日 Web开发, 翻译
Tags: JavaScript, John Resig, jQuery
乔尔谈软件终结篇：分布式版本控制系统的时代到来了
2010年03月20日 编程技术, 翻译
前不久，杰夫、我，还有埃里克一块参加Stack Overflow Podcast的在线聊天。哥几个针对版本控制问题，狠狠地发了一通牢骚。特别是大批特批了以Mercurial和Git为代表的、新潮的DVCS（Distributed Version Control System，分布式版本控制系统）。
聊天中，我说：“我觉得，用它们来做分支和合并更简单，恰恰说明了你的同事可能会做更多的分支和合并。结果呢，就是你会把自己绕进去，最后非晕菜不可。”
说实话，你们也猜得到，参加那种聊天活动，不需要事先准备什么，不过是几个人东拉西扯地闲聊天而已。既然是闲聊天嘛，就免不了说错话，或者用技术术语来说就是——犯错误。要么哪句话里有错误，要么出发点有错误，要么就是出发点和话里都有错误。但这一次，我犯了一个低级错误。就像草莓配比萨、辣椒配面包，属于那种低级得不能再低级的错误。
在这次聊天之前，我们团队已经切换到Mercurial很长时间了，但这次切换真的把我搞晕了，我不得不花钱请人替我check in代码（开个玩笑）。不过，有一段日子我确实不好过，因为我得记住几个关键的命令，想象着自己是在Subversion中使用它们，期待能看到熟悉的结果。可是，一旦碰到结果跟我想象得不一样，我就会大惑不解。为此，我经常得颠儿颠儿地跑到楼下大房间里，请教本杰明或者雅各布。
你猜我的团队怎么说，“哎，乔总，这‘水银果汁’[注1]太神了，我们打算用实际的产品代码来测试一下它。另外，还有，这一点更重要，我们发现了一个大市场，我们可以为它提供有偿技术支持和托管服务。”（Mercurial是基于GPL的自由软件，但有不少公司在决定使用什么之前，总会需要某种支持。）
我心里想，你们问我，我问谁？你们都知道，我在公司并不真正作主，因为“管理的职能就是提供支持”嘛。然后，他们就把所有6名实习生都组织起来，动手开发基于Mercurial的产品。
真不能再拖下去了，我必须得尽快弄明白，所谓的“分布式版本控制”到底咋回事。免得我们公司的产品都上市开卖了，人家让我介绍产品，我自己都说不出个子丑寅卯来。那样的话，博客圈里又会有人跳出来，对我指手画脚，说我糟蹋好东西了（junking the sharp）。
于是，我学呀，学呀，最后终于闹明白了。今天，我想跟大家在这里分享一下。
在分布式版本控制系统中，所谓的“分布式”其实不是最关键的。
最关键的是在使用这些系统时，你时刻要想着“更改”，而不是“版本”。
我明白，这里边其实有几分“道可道，非常道”的意味。在使用传统的版本控制系统时，你会想：嗯，这是版本1，这是版本2，这是版本3。
而在使用分布式版本控制系统时，其实我不用想版本。我只要想，我做了这些更改，我又做了另一些更改。
“程序模型”变了，“用户模型”也得跟着变。
在Subversion中，你可能会想，“要保证我的版本跟主版本随时一致”，或者“恢复到前一个版本”。
在Mercurial中，你会这样想，“看看雅各布的更改”，或者“我们先不用考虑那些更改”。
如果你在使用Mercurial时，心里想的是Subversion，多数情况下倒也问题不大；但是，万一出了问题，你就会找不着北、会不高兴，最后因为无计可施而恨上Mercurial。
可是，如果你能够解放思想，换一个角度来看版本控制，就能悟出管理“版本”与管理“变更”的差异所在。你会觉得豁然开朗，由衷地感叹这才是控制版本的最佳方式。
没错，是有点异样的感觉——从1972年至今，所有人关注的都是怎么管理版本，而今天，人们突然要去关注更改本身了，能不感觉异样吗？而且，关注更改解决了一个非常重要的问题：合并分支代码。
这一点最重要了。没错，在长达10年的时间里，我们深刻地体会到，这一点对提高开发效率最为重要。重要到了什么程度呢？重要到在我今天最后一次谈软件时，必须要反复强调它。好了，如果你只想记住一句话，那就记住下面这句：
在管理更改而非管理版本时，合并很容易做到，你可以根据工作需要随时创建分支，因为合并已经是小菜一碟了。
记不清有多少个使用Subversion的用户，曾对我说过下面这番话：“用它创建分支代码的时候，没什么问题。但是，等到要把分支合并到一块时，那个费劲啊，我们不得不手工重新应用每一次更改。我们发誓，这种蠢事一辈子也不会再干了。结果，我们想出了一个开发软件的新主意，就是用if语句，不用分支。”
有时候，他们在提到自己发明的这种一个主干的做法时，甚至还有几分得意。好像弥补了自己版本控制工具的不足，就可以流芳百世了。
使用分布式版本控制系统，合并简单，还不会出错。所以，你可以创建一个稳定的分支、一个开发分支，还可以为QA团队创建一个长期使用的分支，以便在实际部署之前进行测试。当然，还可以创建一个临时分支，用它来验证各种想法，观察结果。
这一点太重要了，怎么强调它都不算过分。自从我10年前开始写博客以来，这恐怕是我笔下的软件开发技术领域中最大的进步了。
或者，可以换一种说法，如果我要放弃Mercurial，除非是我想再使用C++。
如果你还在使用Subversion，停止使用。马上停止使用。Subversion＝水蛭。Mercurial＝抗生素。我们现在有更好的技术了。
很多人在没有完全理解这种新程序模型的情况下，往往会盲目地使用Mercurial，而这容易让人觉得它有问题，不可靠。为此，我专门写了一套Mercurial教程，叫做HgInit[注2]。
如今，要是有人问我那次聊DVCS时为什么要贬低DVCS，我会告诉他们那是我精心设计一个圈套，我是在放烟雾弹，目的是要迷惑我的老朋友和老竞争对手埃里克——他在开发一个非分布式的版本控制系统。就像上一次他要卖bug追踪软件一样。那一次，为了惩罚他，我们用一个特制的信封寄给他一个非常值钱的Fog Creek双肩背包。让他觉得我们会在圣诞节的时候，也会把这么值钱的背包作为圣诞礼物，送给所有FogBugz软件的客户。
我的博客写到今天，时间已经够长了。10年来，大家能够坚持阅读我写的文章，是我莫大的荣幸。这个博客的读者群能达到今天这个规模，是我当初做梦也想不到的。无论你是谁，是花自己的时间把我的文章翻译成40多种语言的那几百位志愿者中的一员，是给我写过电子邮件的22 894位朋友中的一位，是订阅了我的邮件简报的50 838名订阅者之一，还是每年2 262 384位访问这个站点并阅读了我写的1 067篇文章中哪怕只言片语的读者中的一位，我都要由衷地感谢你，感谢你对我的关注。
本博客专注于Web前后端技术、移动平台开发技术和技术翻译。 
