淺談二分搜尋法

[aszx87410]

前言

在寫程式的時候，其實會滿常用到「搜尋」的功能。
最簡單的搜尋就是在一串數字裡面找出你想要的數字，而這也是我們今天的主題。

這一篇大致上會分成三個部分，第一部分會先介紹線性搜尋法，第二部分介紹二分搜尋法，最後一部分談談二分搜尋法在不同條件底下的實作方式會有什麼不同。

線性搜尋法

為了由淺入深，我們從最基礎的線性搜尋法（Linear search）開始談起。
就如同它的名字一樣，線性搜尋法就是「從頭到尾一個一個找」，時間複雜度為 O(n)，很容易理解也很好實作

function linear_search(array, target){
  for(var i=0; i<array.length; i++){
    if(array[i]==target) return i;
  }
  return -1; //找不到
}

或是可以參考這個簡單的動畫，錄自Algorithm Visualizations

二分搜尋法

假如今天要搜尋的數列是有序的，我們便可以把線性搜尋法再做優化，使時間複雜度再更低一點

二分搜尋法的原理跟小時候大家玩「終極密碼」的流程十分類似
就是那個 1~99 要你猜數字的遊戲

為了快點猜到（或是讓敵人快點猜到），有些人第一個數字會喊 50，為什麼呢？
因為無論數字是小於或是大於 50，剩下的數字一定會砍一半，變成原本的 1/2
假設下一次也繼續這樣砍對半，大概猜個七八次，就能「保證」一定猜得到

這邊可以做個簡單的小驗證：
如果只有 1 個數字，猜 1 次必定猜得到
如果只有 2 個數字，猜 2 次必定猜得到
如果只有 3 個數字，猜 2 次必定猜得到
如果只有 4 個數字，假設是 1 2 3 4 好了
切半猜 2，結果範圍變成 3 4，剩兩個數字，要猜 2 次
所以 4 個數字的話，猜 1 + 2 = 3 次一定猜得到

如果有 8 個數字，切半剩下 4 個，所以要猜 1 + 3 = 4 次
...
這樣繼續推廣下去，就會發現保證能猜到的次數與以 2 為底取 log 有關
詳細數學公式就不再贅述

瞭解原理之後，會發現二分搜尋法的流程也非常簡單：

1. 決定好左邊界 L，右邊界 R
2. 取 M = (L+R)/2，作為中間的 index
3. 如果 array[M] == 要找的數，return M
4. 如果 array[M]>要找的數，表示 M~R 這一段數字都是不可能的，所以讓 R = M - 1
5. 如果 array[M]<要找的數，表示 L~M 這一段數字都是不可能的，所以讓 L = M + 1
6. 如果 R>=L，持續第 2 步，否則回傳 -1（代表找不到）

這邊的停止條件是「當L>R」的時候，就代表找不到了
因為 L 代表：最左邊的有可能的值。換句話說，假如有答案，一定在 >=L 的位置
R 代表的是：最右邊有可能的值，假如有答案，一定在 <=R 的位置
所以當L > R 的時候，>=L 跟 <=R 已經是空集合了，代表不可能有答案

這邊還有一個要特別注意的點是(L+R)/2這句，當值很大的時候可能會造成 overflow。為了避免這種情形，可以改寫成(R-L)/2 + L

可以參考一樣從 Algorithm Visualizations 錄製的簡單動畫

（藍色是 L，黃色是 R，綠色是 M，要找的數字是 180）

function binary_search(array, target) {
  var L = 0, R = array.length - 1;
  while(L<=R) {
    var M = Math.floor((L+R)/2);
    if(array[M]==target){
      return M;
    } else if(array[M]>target) {
      R = M - 1;
    } else {
      L = M + 1;
    }
  }
  return -1;
}

不同條件的二分搜尋法

剛剛所介紹的二分搜尋法，就只是要求在一連串數列裡面回答說有沒有找到，有的話在第幾個位置有
如果數列裡有重複的數字，而且條件變更成：回傳「第一個」出現的位置
例如說 1 2 2 2 2 2 3 3 要找 2，就回傳：1，因為第一個 2 出現在 index 為 1 的地方

或者，改成回傳「最後一個」出現的位置
同樣以上面那個例子來說，要回傳：5，因為 index 5 是最後一個 2

甚至還有稍微更複雜一點的，例如說以下四種：

1. 回傳第一個 >=target 的位置
2. 回傳第一個 >target 的位置
3. 回傳最後一個 <=target 的位置
4. 回傳最後一個 <target 的位置

（可參考：lower_bound）
再搭配上剛剛所說的找等於 target 的第一個與最後一個的位置
可以知道這樣的變形總共有 6 種，那該怎麼辦呢？

其實原理都很類似，一樣是用二分搜尋去排除最多的數字，但是在一些條件判斷上會有些微差異
如果弄得不好的話，很容易會造成無窮迴圈，例如說找最後一個小於target 的數：

function search(array, target){
  var L = 0, R = array.length - 1;
  while(L<=R) {
    var M = Math.floor((L+R)/2);
    if(array[M]<target){
      L = M;
    } else {
      R = M - 1;
    }
  }
  return M;
}

我們拿這一組範例去跑：search([1,2,3,4,5],2)
剛開始 L=0, R=4, M=2
array[2] = 3 > 2，所以 R = 2-1 = 1

接著 L=0, R = 1, M = 0
array[0] = 1 < target，L = M = 0

然後就會再重複一樣的步驟，陷入無窮迴圈
這個就是寫二分搜的時候最常碰到的情況之一
一些條件沒有設定好，或許只是差一個等號或者是+1 -1，但就是搞不定

網路上可以找到許多文章，都是在講解應該要怎麼設定這些條件：

1. 二分查找法的实现和应用汇总
2. 漫谈二分查找-Binary Search
3. 二分搜索法简单分析与总结

或是這篇知乎上的問答也有很多討論可以參考：二分查找有几种写法？它们的区别是什么？
其中我最喜歡的是這個回答：

说到面试，其实这题的难点在于最后边界条件，那么我们根本不用判断那个边界，二分到区间小到一定程度，比如5个元素以下，就顺序查找好了，反正也是O(lgN)的，而且最后5个元素顺序查找平均也只需要比较两三次而已，跟你二分差不多，我本人也很推荐在实际工程中这样写，可以规避很多麻烦的bug，用最稳妥的办法解决问题

這個思路我之前也有想過
既然+-1或者要不要加等號這麼麻煩，那乾脆就不要加了吧！

只要把終止條件改一下，判斷邏輯也改一下就好
一樣舉上面那個：找最後一個小於target 的數為例子

基本上的原則就是：

1. 保證答案一定在閉區間 [L, R] 裡面
2. 當這區間剩下的數很少時，改用線性搜尋

這樣就不用怕碰到無窮迴圈的問題了，下面附上程式碼：

// 傳回最後一個 < target 的數
function lower_bound(array, target) {
  
  // 先看看是否沒答案
  // 如果第一個數還是沒有 < target，代表沒答案
  if(array[0]>=target) return -1;
  
  // 結束條件是區間內剩兩個以下數字的時候
  var L = 0, R = array.length-1;
  while((R-L+1)>2) {
    var M = Math.floor((L+R)/2);
    if(array[M]<target){
      L = M;
    } else {
      R = M - 1;
    }
  }
  
  // 在答案範圍內用線性搜尋
  // 其實到這邊只會剩下兩個元素以內，不一定要用迴圈
  for(var i=R; i>=L; i--){
    if(array[i]<target){
      return i;
    }
  } 
}

就算條件變得不一樣，例如說要找：>=target, <target 等等的，只要改一下條件，用差不多的架構就可以得到解答

結論

其實原本我是想好好研究一下在不同狀況下的二分搜，那些條件到底要怎麼訂，有沒有什麼統一的規則可以參考
但最後覺得還是文末給出的解法最方便，不但好想，而且還好寫
不用去顧慮那些<>=的符號跟+1-1的問題，在執行效率上也差不多

在演算法這一塊我沒有很專業
若是文章之中有哪部分有錯的話，還麻煩各位前輩不吝指正 <(_ _)>

最後附上不嚴謹的測試與各種二分搜版本的 JavaScript 程式碼

[Yuessiah]

感謝大大的分享
我是從這篇讀過來的XD：
https://medium.com/hulis-blog/why-blogging-ab77fd8c6ffa

這裡我也分享一下我對二分搜尋的理解，希望能幫助更多人：
https://ithelp.ithome.com.tw/articles/10207794

但由於我這篇文章是競技程式設計的教學
為引導讀者自己去想，有些地方不會寫的太細(