圖書館自習的時候，一個女生背著一堆書走進閱覽室，結果警報響了。阿姨讓女生看是哪本書把警報弄響了，女生把書倒出來，一本一本地測。阿姨見狀急了，把書分成兩份，第一份過了一下，響了。又把這一份分成兩份接著測，三回就找到了。阿姨用鄙視的眼神看著女生，仿佛在說 O(n) 和 O(log n) 都分不清。
要說哪個算法的知名度較高，二分查找一定排得上號。以至於在面試的時候，如果應聘者簡歷寫了擅長算法或者參加過ACM競賽之類，我都會讓他現場寫一道二分查找的題目：
// 已知array數組的元素為單調非遞減，給定一個target，返回array數組裡面
// 第一個大於或等於target的元素下標，如果沒有合法結果則返回len(array)
func FirstGreaterOrEqual(array []int, target int) int {
// TODO: write your code here
return len(array)
}
一開始我覺得如果對方真的擅長算法，這題應該很基礎並不算為難應聘者(紙上寫只需要偽代碼即可/電腦上寫則需要通過編譯)，直到幾十輪面試之後幾乎90%的人都在這道題上敗北。
後來我認真反思了這個事情，發現從思路上來講，絕大部分人都是沒有問題的：用l和r來表示一個待查找區間，將區間中點m對應的元素同target相比較，根據比較結果來決定繼續查找哪一半。也就是說，大家幾乎都能寫出如下的「骨架」：
func FirstGreaterOrEqual(array []int, target int) int {
// 初始化區間左端點：-1 || 0 || 1 ？
l := 0
// 初始化區間右端點：len(array) - 1 || len(array) || len(array) + 1 ?
r := len(array)
// 當區間不為空時循環：l + 1 < r || l < r || l <= r || l <= r + 1 ?
for l < r {
// 計算區間中點：l + (r - l) / 2 || l + (r - l + 1) / 2 ?
m := l + (r - l) / 2
// 將中點對應的元素同target比較：> || >= || < || <= ?
if array[m] < target {
// 繼續查找右側這一半：m - 1 || m || m + 1 ?
l = m + 1
} else {
// 繼續查找左側這一半：m - 1 || m || m + 1 ?
r = m
}
}
// 這裡應該是 l - 1 || l || l + 1 ?
// 這裡應該是 r - 1 || r || r + 1 ?
return l
}
但是你可能已經注意到了我加的這些注釋，幾乎每一行代碼都有很多的「抉擇」，這使得許多應聘者最終「栽」在了這短短十來行代碼上。後來我又在維基百科上發現了這樣一段話：
儘管二分查找的基本思想相對簡單，但細節可以令人難以招架 —— 高德納
當喬恩·本特利將二分查找問題布置給專業編程課的學生時，90%的學生在花費數小時後還是無法給出正確的解答，主要因為這些錯誤程序在面對邊界值的時候無法運行，或返回錯誤結果。1988年開展的一項研究顯示，20本教科書裡只有5本正確實現了二分查找。不僅如此，本特利自己1986年出版的《編程珠璣》一書中的二分查找算法存在整數溢出的問題，二十多年來無人發現。Java語言的庫所實現的二分查找算法中同樣的溢出問題存在了九年多才被修復。
所以我寫下了這篇文章，希望能夠徹徹底底地講明白我心目中的「二分查找」到底是什麼。在弄懂它的本質以後不管遇到什麼類型的二分查找問題，都能夠準確無誤地寫出正確的代碼。
問題重新定義我們要解決的第一個問題，就是重新定義「二分查找」。為什麼要重新定義，因為它的變種問題實在是太多了：在嚴格單調遞增/非嚴格單調遞增/嚴格單調遞減/非嚴格單調遞減的數組中查找大於/大於等於/小於 /小於等於target的最前一個/最後一個的元素下標。其實這還只是基本變種，一些更為複雜的變種就不在這裡一一列舉了。如果我們針對特定問題去設計特定算法，那你必然會迷失在茫茫多的變種問題裡面。
但是這些問題的解決其實都可以依賴於一個基本問題的解決，可以不嚴格地陳述為：
在一個左邊全是 false 右邊全是 true 的數組中，有且只有一個從 false 突變為 true 的點，二分查找其實就是要找到這個突變點。
我認為比起嚴格的陳述，每當說到二分查找，腦海中自然而然地浮現出上面這幅圖更為重要。在這幅圖所表示的數組中，紅色的格子表示false，藍色的格子表示true。其中格子為深紅色和深藍色表示顏色已經確定，它們是向兩側無限延伸沒有盡頭的。整個數組只有中間淺色的一段還未確定，二分查找其實就是要確定出紅色到藍色的突變點( 這裡不用著急解決各種變種問題，後面會講到如何將它們轉化為這個基本問題)。
區間如何表示問題看起來像是定義清楚了，其實並沒有。阻礙我們的第一個絆腳石就是：待查找區間應該如何表示？當我們說使用l和r來表示這個區間的時候，其實有四種可能
前開後開(l, r)
前開後閉(l, r]
前閉後閉[l, r]
前閉後開[l, r)
到底應該使用哪種來表示其實並沒有關係，理論上使用任何一種都行，只要做到前後一致即可。例如你使用了前閉後閉[l, r]，判斷區間非空就應該寫成r - l + 1 > 0，相反如果你使用了前閉後開[l, r)，判斷區間非空則應該寫成r - l > 0 。就個人喜好而言，我更偏向最後一種：前閉後開[l, r)。
首先說說前開有什麼缺點。例如一個數組array，我們想要表示array[0], array[1], array[2]這段區間，用前開就意味著l = -1 。對於Golang這種語言來說也許算不上什麼問題，但是如果遇到數組下標嚴格要求為無符號整型的語言，你可能將會面臨無窮無盡的類型轉換。相反，選擇前閉則不存在這個問題。
再來說說後閉有什麼缺點。嚴格來說後閉其實沒什麼缺點，只不過當我們計算區間長度的時候，用前閉後閉是d = r - l + 1，用前閉後開則是d = r - l。或者從另一個角度來看，當我們固定l = 0 時，如果想要表示空區間，前閉後閉的情況下r = -1，依然會面臨著無符號整型問題。
因此我偏向使用前閉後開[l, r)。這種情況下，用l < r判斷區間非空，用r - l計算區間長度，用m = l + (r - l) / 2計算區間中點。再次強調，這僅僅代表了個人偏好。
突變點如何表示區間的問題我們算是解決(或者說達成共識)了，下一個問題是突變點如何表示。從之前的圖可以看得出來，我們可以有兩種選擇
用最後一個紅色(F)表示突變點。
用最前一個藍色(T)表示突變點。
同樣的，這兩種選擇誰也沒有錯，但選最後一個紅色作為突變點依然會面臨著F = -1的無符號整型問題，因此我更傾向於選擇最前一個藍色表示突變點。而且由於F和T之間有著明顯的關係F + 1 = T，所以真正需要F 的時候我們也可以通過T將它輕易算出來。
算法核心邏輯當我們把問題重新定義、區間如何表示、突變點如何表示解決以後，整個算法其實已經呼之欲出了。在這之前我們再來嚴格地陳述下這個問題：
這個陳述其實無關緊要，腦袋裡裝下這幅圖，並且理解它，你一定會自己」定義」出這個問題以及」發現」對應的算法實現。
一圖勝千言，我們直接把這幅圖「翻譯」成代碼。儘管只有短短幾行，請務必對照上圖仔細體會。
func BSearch(l, r int, f func(int) bool) int {
for l < r {
// 注意這裡是為了避免溢出
m := l + (r - l) / 2
if !f(m) {
l = m + 1
} else {
r = m
}
}
return l
}
關於正確性和複雜度分析，在這裡說」顯然」其實一點都不為過。不過我還是用數學歸納法來證明一下正確性，至於複雜度分析就留給讀者了。
當d = r - l = 0時，代碼不會進入for循環，直接返回l。由問題嚴格陳述的第3點我們知道f(l - 1) = false和f(r) = true，又因為此時l = r，所以直接返回l就是正確的答案。
假設對於所有的d = 0, 1, 2, ..., k - 1，該算法都能返回正確的答案l。那麼當d = k時，代碼將會進入for循環，此時中點m ∈ [l, r)。這時候分兩種情況：
綜上，在這兩種情況下，我們都可以在滿足問題嚴格陳述的第3點前提下，將區間長度d變小，轉化為一個已經被證明可解決的問題。
解決變種問題回到最開始的面試問題
// 已知array數組的元素為單調非遞減，給定一個target，返回array數組裡面
// 第一個大於或等於target的元素下標，如果沒有合法結果則返回len(array)
func FirstGreaterOrEqual(array []int, target int) int {
// TODO: write your code here
return len(array)
}
這再簡單不過了吧，我們只需要將f(x)定義為array[x] >= target是不是就可以了，因此它的實現代碼可以是這樣
func FirstGreaterOrEqual(array []int, target int) int {
return BSearch(0, len(array), func(x int) bool {
return array[x] >= target
})
}
至於其他變種問題呢，如法炮製，核心就是想辦法把問題轉化成基本問題中的布爾數組。掌握了這一點，就可以說是掌握了二分查找的精髓。
// 問題: array 非嚴格遞增，返回第一個大於 target 的元素下標。
// 補充: 如果查找不到合法結果，則返回 len(array) 即可。
func FirstGtInAsc(array []string, target string) int {
return BSearch(0, len(array), func(x int) bool {
return array[x] > target
})
}
// 問題: array 非嚴格遞增，返回第一個大於等於 target 的元素下標。
// 補充: 如果查找不到合法結果，則返回 len(array) 即可。
func FirstGteInAsc(array []string, target string) int {
return BSearch(0, len(array), func(x int) bool {
return array[x] >= target
})
}
// 問題: array 非嚴格遞增，返回最後一個小於等於 target 的元素下標。
// 補充: 如果查找不到合法結果，則返回 -1 即可。
func LastLtInAsc(array []string, target string) int {
return BSearch(0, len(array), func(x int) bool {
return array[x] > target
}) - 1
}
// 問題: array 非嚴格遞增，返回最後一個小於 target 的元素下標。
// 補充: 如果查找不到合法結果，則返回 -1 即可。
func LastLteInAsc(array []string, target string) int {
return BSearch(0, len(array), func(x int) bool {
return array[x] >= target
}) - 1
}
// 問題: array 非嚴格遞減，返回第一個小於 target 的元素下標。
// 補充: 如果查找不到合法結果，則返回 len(array) 即可。
func FirstLtInAsc(array []string, target string) int {
return BSearch(0, len(array), func(x int) bool {
return array[x] < target
})
}
// 問題: array 非嚴格遞減，返回第一個小於等於 target 的元素下標。
// 補充: 如果查找不到合法結果，則返回 len(array) 即可。
func FirstLteInAsc(array []string, target string) int {
return BSearch(0, len(array), func(x int) bool {
return array[x] <= target
})
}
// 問題: array 非嚴格遞減，返回最後一個大於等於 target 的元素下標。
// 補充: 如果查找不到合法結果，則返回 -1 即可。
func LastGtInAsc(array []string, target string) int {
return BSearch(0, len(array), func(x int) bool {
return array[x] < target
}) - 1
}
// 問題: array 非嚴格遞減，返回最後一個大於 target 的元素下標。
// 補充: 如果查找不到合法結果，則返回 -1 即可。
func LastGteInAsc(array []string, target string) int {
return BSearch(0, len(array), func(x int) bool {
return array[x] <= target
}) - 1
}
當然除了基本變種，還有很多其他類型的變種，未必都能完全套到這個基礎問題上來。但是大差不差，做一些輕微的調整大多數都是能輕易解決的。如果實在遇到解決不了的問題，希望這篇文章中的某些點可以為你提供啟發性的思路。
寫在最後我真的不是標題黨，二分查找確確實實是個一看就會一寫就跪的問題。包括幾乎90%的面試者都在這道題上敗北，也同樣是真實數據。寫這篇文章主要參考了Golang的sort.Search和C++的std::lower_bound，後者的實現考慮得更為全面一些，只需要迭代器是ForwardIterator就行了，不依賴隨機尋址甚至不依賴向前尋址，相當優雅。