一個(gè)偶然的機(jī)會(huì)，我想起以前還在谷歌上班的時(shí)候，有時(shí)候大家會(huì)在飯桌上討論最新想出來的一些面試題。在眾多有趣又有難度的題目中，有一道老題卻是大家都紛紛選擇避開的，那就是去實(shí)現(xiàn)二分查找。

因?yàn)樗芎脤?，卻很難寫對(duì)?？梢韵胂髥柫诉@道題后，在5分鐘之內(nèi)面試的同學(xué)會(huì)相當(dāng)自信的將那一小段代碼交給我們，剩下的就是考驗(yàn)面試官能否在更短的時(shí)間內(nèi)看出這段代碼的bug了。

二分查找是什么呢，這個(gè)不只程序員，其他很多非技術(shù)人員也會(huì)。比如我想一個(gè)1到100以內(nèi)的數(shù)，你來猜，我告訴你每次猜的是大了還是小了，你會(huì)先猜50，然后25， 然后。。。用不了幾個(gè)問題就猜出來了。1到100范圍太小的話，我們放大點(diǎn)猜個(gè)人名，你問中國人外國人，古代人現(xiàn)代人，男的女的，用不了幾個(gè)問題也問出來了。在計(jì)算機(jī)里，則是在一個(gè)有序數(shù)組里面，不斷通過二分的方法縮小關(guān)鍵字的可能下標(biāo)范圍。當(dāng)然了，我們不一定在一個(gè)有序數(shù)組里查找，也可以在一個(gè)很大的狀態(tài)空間里，去查找一個(gè)單調(diào)函數(shù)的取值。這樣的做法，似乎編個(gè)程序很容易實(shí)現(xiàn)，但是，

D.Knuth大神說了：Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky 雖然二分查找的基本思想相對(duì)來說很直接，但具體實(shí)現(xiàn)起來有特別多的坑。

另一位大神，編程珠璣的作者Jon Bentley，他做了我們?cè)谖恼麻_頭不敢做的事，他布置作業(yè)讓他的學(xué)生們寫二分查找，然后他一個(gè)個(gè)來看。結(jié)果呢，他發(fā)現(xiàn)90%是錯(cuò)的。因此在他的編程珠璣這本書中，專門有一章講解了二分查找，雖然他的范例仍然是錯(cuò)的，見下面的Java Bug。埋下這個(gè)bug的人，也正式Jon Bentley的學(xué)生。

還有好事者，更是找了許多教科書，發(fā)現(xiàn)20本教科書里面，只有5本是寫對(duì)了的，于是他發(fā)了一篇文章到ACM。當(dāng)然這是早在1988年的時(shí)候。

然而這些都不算啥，更能讓人感覺幸災(zāi)樂禍的是，Java庫里面的二分查找，有一個(gè)埋藏了10年之久的bug。這個(gè)bug呢，在 java.util.Arrays.binarySearch 里面，雖然這個(gè)bug的修復(fù)也已經(jīng)是10年前的事了。那么我們來看下當(dāng)年的錯(cuò)誤代碼吧。

大家可能很難看出來，那畢竟這個(gè)bug藏了10年，不太容易發(fā)現(xiàn)。問題就在于

1

int mid = (low high) / 2;

這里。low high 是會(huì)溢出的。只要這個(gè)數(shù)組我們開的足夠大，比如1100000000，就能重現(xiàn)這個(gè)問題，雖然這需要我們費(fèi)點(diǎn)內(nèi)存。因此正確的解法是：int mid = (low high) >>> 1; 三個(gè)>，無符號(hào)位移的意思。正如修復(fù)bug的同學(xué)說的那樣：

1

"Can't even compute average of two ints" is pretty embarrassing.

這個(gè)bug的鏈接在這里。

那么我們究竟如何來把二分查找寫正確呢？我們二分查找中常見的錯(cuò)誤除了上面的溢出之外，最多的是下面幾類：

差1錯(cuò)誤。我們的左端點(diǎn)應(yīng)該是當(dāng)前可能區(qū)間的最小范圍，那么右端點(diǎn)是最大范圍呢，還是最大范圍 1呢。我們?nèi)×酥虚g值之后，在縮小區(qū)間時(shí)，有沒有保持左右端點(diǎn)的這個(gè)假設(shè)的一致性呢？
死循環(huán)。我們做的是整數(shù)運(yùn)算，整除2了之后，對(duì)于奇數(shù)和偶數(shù)的行為還不一樣，很有可能有些情況下我們并沒有減小取值范圍，而形成死循環(huán)。
退出條件。到底什么時(shí)候我們才覺得我們找不到呢？
我很喜歡二分查找這個(gè)案例。一個(gè)在理論上這么簡單直接的算法，在計(jì)算機(jī)里實(shí)現(xiàn)卻要考慮那么多實(shí)際的情況，除了理論的細(xì)化比如差1錯(cuò)誤和退出條件，還有計(jì)算機(jī)的實(shí)際問題如整除2，死循環(huán)，以及上面提到的溢出。正如我們以前同事每天掛在嘴邊的

You know the difference between in theory and in practice? In theory there’s no difference but in practice there are.

軟件工程師，就是把現(xiàn)實(shí)生活用理論進(jìn)行建模，然后再用現(xiàn)實(shí)來實(shí)現(xiàn)這樣的理論。寫出好的代碼不容易，寫出既讓用戶滿意又好的代碼，那更不容易。也許有時(shí)候，成就感就來自于此吧。

歡迎工作一到五年的Java工程師朋友們加入Java架構(gòu)師：697558955

群內(nèi)提供免費(fèi)的Java架構(gòu)學(xué)習(xí)資料（里面有高可用、高并發(fā)、高性能及分布式、Jvm性能調(diào)優(yōu)、Spring源碼，MyBatis，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個(gè)知識(shí)點(diǎn)的架構(gòu)資料）合理利用自己每一分每一秒的時(shí)間來學(xué)習(xí)提升自己，不要再用"沒有時(shí)間“來掩飾自己思想上的懶惰！趁年輕，使勁拼，給未來的自己一個(gè)交代！