二分搜尋法（Binary Search）完整教學（六）
從 source code 中學習
系列連結
這篇讓我們來看看 c 與 python 的 source code，學習他們是怎麼實作 binary search 的。跟我們前幾篇講的又有什麼差別，首先來看看 python 的 bisect lib。
首先，他的 lo 與 hi 就是我們的 left 與 right，而我們發現了幾個和之前的不同之處
- 為什麼他的 hi 定義為 array 的 length，而不是 length -1 ?
- 他的 while 裡面怎麼是 < 而不是 <=？
- 為什麼他在 else case 裡，是 hi = mid 而不是 hi = mid-1？
要回答這幾個問題，來回想我們第一篇文章講的閉區間這件事，你就會發現他們全部都只是區間定義上的差異。我們之前定義的搜尋區間，是包含 left 與 right 兩個端點的，數學表達式會是 [left, right]，但在 python 的 source code 中的定義方式是包含 left 端點，但不包含 right 端點，數學表達式會變成 [left, right)，也就是左閉右開區間，如此以上三個問題的回答就非常簡單了。
因為不包含 right 端點，所以：
- 初始的 right 位置，應該被放在最大 index +1（也就是 array 長度）。
- 當 left == right 時，我們無法既包含 left 又不包含 right，所以當這情境發生，答案已經不存在了，也就可以直接停止搜尋。
- 只需把 right 移動到 mid 的位置，就已經自然把 mid 的位置從區間內排除了，而不必再 -1。
事實上，這種左閉右開區間，也是滿多人喜歡的選擇，其實我們早就見過了這種區間定義方式，請看以下例子。
for (int i = 0; i < N; i++) {
// do something
}有沒有很熟悉？為什麼我們不寫 <= N-1，而是寫 < N，其實也就是一種習慣而已。python 中的 range 也採用了同樣的定義方式。另外他也有些實際好處，例如兩個相鄰區間，中間值會一樣，我可以把 [0, 4) 切成 [0, 2) 跟 [2, 4)兩半，這時候用左閉右開區間確實讀起來方便些，再者，這種區間的長度也會剛好等於左右值相減。
不過，最終就只是個人選擇而已，我自己還是覺得閉區間讓我比較好想清楚，但不論你想用哪套，只要釐清觀念並嚴格遵守即可。每個工程師都該有一套自己熟練的 binary search 寫法，這樣才不會遇到問題時，浪費一堆時間在這些邊界條件上，甚至還寫錯，還得靠一堆例子去 debug ，這樣就太辛苦了。
有興趣的朋友可以用左閉右開區間的定義，把前面提到的問題都重寫一次，假如你有搞懂，就不是太困難，也是個很好的自我測驗方式。。
再來，我們來看看 c++ 的 stdlib 裡面的 lower_bound 是怎樣做的。
這個做法乍看之下令人難以理解，似乎跟我們前面講的完全不同，找不到相似的痕跡。其實是因為他又用了另一套觀念來思考這個問題。來看看他是怎樣理解 binary search 這個問題吧！
當我們有一個數列，我們原本想要做的事情是
- 找到中心點的 value
- 和 target 比大小，比完決定要留下左半還是右半
- 在留下的那一半裡，重複步驟 1
但讓我們換一個想法，也可以改成這樣做
- 我們從起點 0 出發
- 不論在哪，每次想要再往前走一步
- 這個步伐的距離，一開始會設定成 N/2（N 是 array 長度)
- 假如用現在的步伐，會走過頭（讓 value > target），就不要走，否則就用此步伐前進一次
- 讓步距減少一半，重複 2
註：std::advance 就是那個往前走的意思，而 >> 1 則是除以二並無條件捨去的意思（用二進位的思考方式，把最右邊的 bit 移除，其餘皆往右 shift 一格）
稍微想一下，會發現這想法有他的妙處，就是很直線的不斷往前走而已，不用再去思考到底往左還是往右，而且效能也是一樣的。如果覺得前面幾篇文章的 binary search 解釋都讓你理解的很痛苦，這個思路或許也是可以嘗試的方法，看能不能從他去想通 lower_bound 與 upper_bound 的實作方式。
結語
有沒有發現，binary search 的做法還真的很多種，但殊途同歸，大家解決的都是一樣的問題。對大多數人來說，只要熟悉一種定義方式，還有其對應的寫法會有怎樣的性質，就可以做出各種相關的變化題型了。
