二分搜尋法（Binary Search）完整教學（一）

基礎介紹

Published in

AppWorks School

7 min readSep 10, 2020

Binary Search，中文又稱作二分搜尋法，大概是每個初學演算法的人最早碰到的課題。他的觀念極簡單，實作也不複雜，但隨著學習更加深入，會發現這東西版本很多，大家寫起來往往有細微差異，而可以應用的題型也多不勝數，但每個題型到底要使用哪個版本，又有一堆令人頭疼的小細節。

今天這系列文章就來聊聊這個經典演算法的許多眉眉角角，與藏在細節裡的魔鬼，最後帶大家看看 source code 與實戰題目。如果你是剛看懂 Binary Search 的初學者，希望看完本篇後能理解的更透徹，如果你已經很進階了，也歡迎一起討論或指出更多的想法。

實作

首先，來看看 Binary Search 的最簡易版本：

定義：在排序好的數列裡，找某 target，找到就回傳其 index，否則回傳 -1

上面就是最基本的版本，如果你以前完全沒看過這個演算法，可以先試著靜下心來花點時間閱讀一下程式碼，大概能感覺他在做什麼即可，如果還是有點困難的話，下面我給一個比較概念性的解釋，先理解到這樣即可。

left = 左邊的邊界
right = 右邊的邊界
while (左比右小，代表邊界還正常) {
  mid = 左右邊界的中間點
  if (數列中間點的數值大於 target) {
    右半邊可以不用看了，因此把右邊邊界移到中間(mid)
  } else if (數列中間點的數值小於 target) {
    左半邊可以不用看了，因此把左邊邊界移到中間(mid)
  } else {
    找到答案了！
  }
}

接下來，我們開始來關注幾個有趣的細節

問題

最上面的 while 迴圈裡面，為什麼我們要寫 left <= right，不能只寫 left < right 嗎？或說，當 left == right 時，需要繼續嗎？
right 的起始點為什麼是 array 的長度 -1，不能直接是 array 長度嗎？
中間判斷邊界移動時，為什麼是 right = mid-1 跟 left = mid+1，如果不要 -1 跟 +1 或只有其中一邊+-1，會出錯嗎？

有興趣的朋友可以試試看，很神奇的，如果只做 1 或只做 3 的改動都會讓你陷入無窮迴圈，2 更可能直接報錯，即使沒有也暗藏凶險。回答這個問題前，我們先釐清兩個重點：

重點 1：left 跟 right 的精確定義很重要！

先簡單介紹一下，我們一般定義區間時，會分開區間與閉區間，代表的是有沒有包含兩端點，數學上會分別用中括號和小括號表示，看個例子就很好懂

a. [3, 5]: 閉區間，代表 3, 4, 5 （包含 3、5）

b. (4, 9): 開區間，代表 5, 6, 7, 8 （不包含 4、9）

c. [1, 6): 左閉右開區間，代表 1, 2, 3, 4, 5 （包含 1、卻不包含 6 )

所以上面 Binary Search 的寫法中的 left 與 right 代表的就是：答案還有可能存在的區間的兩端點，並且這是個閉區間，也就是 left 與 right 這兩個端點都包含在區間內，數學表達式會是 [left, right]，如下圖。

註：開區間的寫法也有，在續篇會講到

重點 2: mid 在除不盡的狀況，到底會選哪個位置？

今天的 int mid = (left + right) / 2，意思是我要取 (left + right) / 2 的 integer 值，而 integer 是沒有小數點的，所以他會被無條件捨去，例如當我要找 index 為 0 與 index 為 5 的中心點，我會找到 index 為 2.5，經過無條件捨去，最後就是 index 為 2 (也就是 value 是 4 的那個位置），也就是當我除不盡的時候，我要用中間偏左邊的那個位置代表中間點。如下圖。

註1：假如是 python，我們會寫 mid = (left + right) // 2，一樣是無條件捨去的意思。javascript 則是 mid = Math.floor((left + right)/2)。

註2：如果你想全部用中間偏右邊當 mid 值，也是可以的，但未來有些變化型會出現差異，留在續篇再談。至於改法，就留給大家想想。而選中間偏左邊是比較多人的習慣，畢竟稍稍好寫那麼一點點。

註3：更細心一點的人會發現，left + right 有可能不小心就溢位了，超出了整數的數值範圍，但 mid 是不可能溢位的，因此很多人會用 left + (right - left) / 2 這個更安全的寫法。

解答

現在我們可以來回答上面三個問題了，問題的答案其實都是一樣的：因為我們定義的 left 與 right 是閉區間，也就是包含 left 端點與 right 端點。

問題 1 的答案：當我們 left == right 的那一刻，例如 left == 3、right == 3 好了，那代表可能答案會在 [3,3] 之間，這是個合理的區間，且區間裡只有唯一的一個元素（就是在位置 3 的這個），所以當然要再跑一次，確定他是不是我們要的答案，因此 while 的判斷式會是 <= 而非 <。

問題 3 的答案：為什麼要 +-1，同理，因為我們定義的區間是閉區間，假如 mid 不是答案，那 mid 必須被排除在可能是答案的區間裡，因此不需要再考慮他，直接用 [left, mid-1] 或 [mid+1, right] 當成新的區間即可。

問題 2 的答案：需要一點細心觀察，假如今天我們把 right 定義成 array 長度，也就是”最大的可能 index” + 1 的位置上，首先當然違反了閉區間的原則，因為”最大的可能 index” + 1 不可能是答案，不然就超出 array 範圍了。實際操作時，假如我們的 target 大於 array 裡面最大元素的值，例如 target = 11，我的左邊界就會不停的往右移動 mid+1, mid+1,…，最終他會跑到 left == right，且兩個都停在最大的 index +1，還記得 left == right 的時候我們要再跑一次，而此時 mid 的計算方式會讓我們得出 mid == left 的結果，最終我們的 nums[mid] 就會訪問一個超出範圍的位置，這顯然是很危險的，有些程式語言直接報錯，有的則會給你任意可能的回答，讓你以為沒問題，其實更加危險。