潛伏九年的 bug：Java 標準函式庫的 binarySearch 是怎麼壞掉的
一個教科書等級的錯誤
2006 年 6 月 2 日，當時任職於 Google 的 Joshua Bloch 在 Google Research Blog 上發表了一篇標題聳動的文章：〈Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken〉（號外號外：幾乎所有的二分搜尋和合併排序都是壞的）。
這個標題乍看之下像是釣魚，但內容卻讓無數工程師背脊發涼。Bloch 指出：包括他本人為 Java Development Kit（JDK）親手寫的 java.util.Arrays.binarySearch，以及 Jon Bentley 在經典著作《Programming Pearls》（程式設計的實踐藝術）裡示範的版本，統統帶著同一個隱藏的錯誤。
這不是什麼冷門邊角函式。二分搜尋是資訊科學裡最基本、最被反覆驗證、幾乎被視為「不可能寫錯」的演算法之一。它出現在每一本演算法教科書的前幾章，是面試白板題的常客。而 Java 這樣一個被全世界數以百萬計的程式依賴的標準函式庫，它的二分搜尋實作竟然藏著 bug——而且從釋出到被公開指出，中間隔了將近九年。
更諷刺的是：寫出這個 bug 的人，正是 Java 集合框架（Collections Framework）的主要設計者、《Effective Java》的作者 Joshua Bloch 本人。而他所參考的錯誤源頭，還能一路追溯到 Bentley 在 1980 年代的著作。也就是說，這個 bug 的血緣其實橫跨了約二十年，只是在 Java 標準函式庫裡「正式服役」了將近九年才被抓出來。
先回顧：二分搜尋到底在做什麼
二分搜尋解決的問題很單純：在一個已排序的陣列裡，找出某個目標值的位置。
它的策略是「每次砍一半」。維護一段搜尋區間 [low, high]，看區間正中間的元素：
- 如果中間元素剛好等於目標，找到了；
- 如果中間元素比目標大，答案只可能在左半邊，於是把
high縮到中點左邊； - 如果中間元素比目標小，答案只可能在右半邊，於是把
low移到中點右邊。
因為每一步都把搜尋範圍砍半，所以在 n 個元素裡搜尋只需要大約 log₂(n) 次比較。十億個元素，也不過三十次上下。這種對數等級的效率，正是二分搜尋如此重要的原因。
一個典型（帶著 bug）的 Java 實作長這樣：
public static int binarySearch(int[] a, int key) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2; // ← 問題就在這一行
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // 找到目標
}
return -(low + 1); // 沒找到，回傳插入點
}
邏輯完美無缺。它會終止，它會給出正確答案，它通過了幾乎所有你能想到的測試。問題只有一個，而且藏在最不起眼的地方：計算中點的那一行。
bug 在哪裡：(low + high) / 2 的致命之處
int mid = (low + high) / 2;
數學上，這行程式碼絕對正確：兩個索引相加除以二，就是它們的中點。任何人在紙上驗算都不會有問題。
但電腦不是在紙上算數學。在 Java 裡，int 是一個 32 位元的有號整數，它能表示的最大正值是 2³¹ − 1，也就是 2,147,483,647（約 21.4 億）。一旦某個 int 的運算結果超過這個上限，它不會自動變成更大的數字，而是會「繞回去」（wrap around）變成負數——這就是所謂的整數溢位（integer overflow）。
現在想像 low 和 high 都是很大的正整數。它們各自都還在 int 的合法範圍內，看起來一切正常。但問題是它們的和：
low = 1,500,000,000high = 2,000,000,000
兩個都是完全合法的 int。但相加後 low + high = 3,500,000,000，這遠遠超過了 int 的上限 2,147,483,647。
於是溢位發生了。這個 35 億的真實數值，在 32 位元有號整數裡被「繞」成了一個負數：−794,967,296。再除以二，得到 −397,483,648——依然是負數。
接著這個負數被拿去當陣列索引：
int midVal = a[mid]; // a[-397483648] → ArrayIndexOutOfBoundsException
程式當場拋出 ArrayIndexOutOfBoundsException 而崩潰。它不會給你錯誤的答案（那還算某種「靜默的錯」），它會直接爆炸。
我用一段模擬 32 位元運算的程式驗證了這個過程，數字完全吻合：
low + high 的真實值 = 3,500,000,000
溢位成 int32 後 = −794,967,296
除以二（bug 版） = −397,483,648 ← 負索引，程式崩潰
INT_MAX = 2,147,483,647
為什麼九年都沒人發現？
這才是整個故事最耐人尋味的地方。這麼嚴重的 bug，為什麼能潛伏這麼久？
答案是：觸發它需要一個在當年幾乎不存在的條件——一個超過十億個元素的陣列。
要讓 low + high 溢位，兩者之和必須超過 2³¹ − 1。在搜尋接近結束、區間縮到陣列尾端時，low 和 high 都會接近陣列長度。所以粗略地說，這個 bug 只在陣列長度達到大約 2³⁰（約 10.7 億） 或更大時才會現形。
Bloch 在文章裡說得很直接：在《Programming Pearls》寫成的 1980 年代，一個十億元素的陣列是「不可思議」（inconceivable）的。當時一台電腦的整個記憶體都遠遠裝不下這麼大的 int 陣列——光是十億個 int 就要 4 GB 記憶體。沒有人能夠在那個年代真正餵給二分搜尋一個大到會溢位的輸入，這個 bug 自然也就永遠不會被觸發。
於是它成了一個典型的「潛伏 bug」：
- 邏輯上正確——任何 code review 都挑不出毛病，因為它在數學上就是對的；
- 測試上安全——沒有人會為了測二分搜尋而去配置一個 10 GB 的陣列，一般的單元測試永遠碰不到那個邊界；
- 理論上乾淨——它甚至通過了形式化推理，Bentley 在書裡還「證明」過這段程式碼的正確性。
問題不在於程式碼與它所宣稱的邏輯不符，而在於那個邏輯本身悄悄假設了「整數運算不會溢位」——一個在真實的、有限位元的機器上並不成立的前提。這是抽象（理想的無限整數）與實作（有限的 32 位元）之間的裂縫。
隨著硬體演進，到了 2000 年代中期，Google 這類公司開始例行處理超過十億筆資料的陣列。曾經「不可思議」的輸入變成了日常，於是這個沉睡了近九年的 bug 終於甦醒，讓 Bloch 得以把它揪出來公諸於世。
怎麼修：三種寫法
好消息是，修正非常簡單。核心思路是：不要去計算那個可能溢位的和。
修法一：先取差，再加回去
int mid = low + (high - low) / 2;
這是最直觀、最推薦、也最容易讀懂的寫法。它的巧妙之處在於：high - low 是兩個索引的差，而差永遠不會超過陣列長度，所以絕對不會溢位（因為 high >= low，這個差還一定是非負的）。把這個差的一半加回 low，就得到了正確的中點，而且整個過程中沒有任何一步的中間結果會超出 int 範圍。
代入前面的例子：1,500,000,000 + (2,000,000,000 − 1,500,000,000) / 2 = 1,750,000,000，完全正確。
修法二：無號右移
int mid = (low + high) >>> 1;
這是 Bloch 在文章中特別提到、被 Sun 採用進 JDK 的版本。它看起來有點反直覺：low + high 明明還是會溢位啊？
關鍵在於 >>> 這個運算子——它是 Java 的無號右移（unsigned right shift）。即使 low + high 溢位、最高位（符號位）被進位污染而讓這個數「看起來」是負的，但那 32 個位元裡儲存的其實仍然是真實和的低 32 位（因為兩個非負且小於 2³¹ 的數相加，真實結果一定塞得進 32 位元的無號範圍）。無號右移會把符號位也當成一般的數值位來處理，右移一位剛好就是「除以二」，於是還原出正確的中點。
代入例子：(low + high) >>> 1 一樣得到 1,750,000,000。
這個寫法更精簡、也更快（位移比除法快），但可讀性較差，需要對位元運算有一定理解才看得懂為什麼是對的。對於絕大多數應用層的程式碼，修法一是更好的選擇；修法二則適合對效能斤斤計較的函式庫底層。
修法三：用更大的型別
在其他語言或情境中，也可以把中間計算提升到更寬的整數型別（例如 C/C++ 裡用能容納更大值的型別，或明確做寬化轉換），讓和不會溢位。這在跨語言移植時值得留意，但在 Java 這種 int 索引的脈絡下，修法一與修法二已經足夠且更自然。
我把三種正確寫法都驗算過，在會讓原版崩潰的輸入下，它們都穩定回傳正確的中點 1,750,000,000。
不只是二分搜尋
Bloch 在文章標題裡把「合併排序」（mergesort）一起點名，不是順口。同樣的溢位陷阱潛藏在任何需要計算「兩個索引中點」的地方——合併排序在遞迴切分陣列時、快速排序某些實作在選 pivot 時、各式各樣的分治演算法，只要出現 (low + high) / 2 這個慣用寫法，就都可能中招。
這也是為什麼這篇文章的影響力遠超過「修好一個函式」本身。它是一則關於軟體工程本質的寓言。
這個故事教會我們什麼
第一，「正確的邏輯」不等於「正確的程式」。 這段程式碼在數學上無懈可擊，甚至被形式化地證明過。但證明所依賴的前提——整數運算的行為像理想的無限整數——在真實機器上並不成立。抽象與實作之間的每一道縫隙，都是 bug 的溫床。
第二，測試無法覆蓋你想不到的輸入。 沒有人寫得出觸發這個 bug 的單元測試，因為觸發它的前提（十億元素陣列）在很長一段時間裡根本無法被建構。這提醒我們：邊界條件、極端規模、整數上下限，這些「平常不會發生」的情況，恰恰是最危險的。
第三，程式碼會活得比它的假設更久。 Bentley 寫下那段程式碼時，「十億元素的陣列」是科幻。但程式碼不會知道時代變了。當硬體規模跨過某條線，一段沉睡二十年的假設就會突然變成一顆地雷。今天我們寫下的每一個「這種情況不可能發生」，都可能在未來某一天被硬體或資料規模的成長證明為錯。
第四，權威與資歷不是免疫。 這個 bug 出自 Java 集合框架的設計者之手，血緣可溯至演算法界公認的經典教材。它躲過了無數雙眼睛的審視。這不是誰粗心的問題，而是說明了：某些錯誤是系統性的、結構性的，光靠「找個更厲害的人來看」並不能保證抓到。
Bloch 在文章結尾寫下一句常被引用的話，大意是：仔細思考、謙卑，並且測試你的程式碼，因為就連最基本、被研究得最透徹的演算法，在你手裡都可能是壞的。
一行 (low + high) / 2，看起來人畜無害，卻濃縮了軟體工程裡最深刻的教訓之一。下次當你在某段程式碼裡看到兩個數相加，也許值得停下來多想三秒：它們，會不會溢位？
參考資料
- Joshua Bloch, 〈Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken〉, Google Research Blog, 2006 年 6 月。
- Jon Bentley, 《Programming Pearls》——最早示範（也最早埋下）此二分搜尋寫法的經典著作。