前幾天有位朋友跟我反應，二分搜尋法好難寫啊。有的時候寫下去，甚至無法確定這樣寫會不會對，只能祈禱線上提交的時候會順利拿到 Accepted。這樣的想法是很危險的！你不應該仰賴評測系統給你的反饋，才能知道自己是不是對的。至少在上傳之前，思考一下正確性，讓自己更安心。
先說結論
在繼續介紹各種二分搜的方法與證明之前，我想要先下個結論：每個人都應該要有一套屬於自己的二分搜尋法。而且 只用 這套屬於自己的二分搜尋法。
二分搜的概念
假想你有一個只有 0 和 1 兩種數字的陣列，然後所有的 0 都排在 1 的前面。
要如何找出第一個 1 的位置呢？想法很單純，我們戳一個中間的格子，如果這個格子是 0，代表「所有這個格子之前（包含這個格子）都不是答案」。如果這個格子是 1，則代表「所有這個格子之後（不包含這個格子）也不是答案」。於是我們得到一個演算法：
1. 戳一個中間的格子 X
2. 如果 X = 1，那麼把這個格子右邊的所有格子丟掉
3. 如果 X = 0，那麼把這個格子本身與其左邊所有格子丟掉
4. 重複以上操作
這個演算法什麼時候會停？它不會停，因為從上面的演算法描述，我們並沒有叫他停下來。那什麼時候應該要停下來？顯然每一次操作的過程中，左邊丟掉的格子們都是 0、右邊丟掉的格子們都是 1。我們可以把這個觀察寫成重要的迴圈不變量。在迴圈結束後，如果只剩下一個格子，而這個格子是 1，那麼根據演算法來說我們永遠不會把這個格子丟掉。而根據迴圈不變量，我們就保證了這格就是我們要的第一個 1。反之，如果這個格子裡面的數字是 0，那麼根據演算法，下一步這格就會被丟掉，而我們也可以推斷出「這陣列不存在 1」。
二分搜的實作
但是實際寫成程式碼就很怪了啊。到底我們要怎麼表示目前的邊界（或是紀錄被丟掉的格子）呢？因為剩餘的格子們是連續的一段，我們可以利用兩個變數 $\ell$ 和 $r$ 來表示這個區間 $[\ell, r]$。有些人喜歡半開半閉區間 $[\ell, r)$，也就是說當我們存入兩個變數 $\ell$ 和 $r$ 的時候，實際有效的陣列範圍是 $[\ell, r-1]$。那樣寫沒什麼壞處，而且也巧妙地利用了當 $l+r$ 是奇數時 $(l+r)/2$ 向下取整的特性，讓中間值 $m$ 可以留在 $[\ell, r-1]$ 這個區間裡面。不過我自己的習慣是使用閉區間。
我自己的習慣
我的寫法是閉區間的寫法，而且總是維護當前找到的答案候選。引入一個變數 ans，一開始把它標記為「不存在」，如果我找到一個滿足條件的格子（比方說，這個格子必須是 1）那麼在找到的當下，我會更新 ans 的值。讓變數 $\ell, r$ 永遠只用來表達邊界，不要賦予他們過多的意義。
int lower_bound(int array[], auto predicate_fn) {
int l, r, ans = -1;
while(l <= r) {
int m = (l + r) / 2;
if (predicate_fn(array[m]) == true) {
// 如果滿足條件，就把右邊丟掉，並且把當前資料加入可能的答案裡。
ans = m;
r = m - 1;
} else {
// 如果不滿足條件，就把左邊丟掉。
l = m + 1;
}
}
return ans;
}