2015
Jun
17

Binary Search 是一個很有效率的演算法,簡單的應用可以用處理 list 的搜尋,找到 list 中的某一個 item , 搜尋方式為不斷的對 list 剖半再剖半,直到你找到正確的 item 。

Binary Search 可以用在哪呢? 舉例來說,假設天空中有 2 萬顆星星,每個星星都有一個唯一的名字,我們該如何從 2 萬顆星星中,搜尋到我要的那一顆呢,若是使用暴力破解 forloop 的方式來搜尋,平均要搜尋 1 萬次才能找到我要的那顆; 若是使用 Binary Search ,則最慢只要 15 次就一定能夠搜尋到我要的星星資料。

15 次 與 1萬次的差別,從這個例子就能看出演算法的重要性!

猜數字遊戲

接著就讓我來介紹 Binary Search 如何運作,Binary Search 第一步就是要合理的去猜測一個 List 裡最中間的數字,例如有一個 1 ~ 100 的猜數字遊戲 ,如果你第一值猜 25 ,那麼我會跟你說「高一點」,接著你可能會猜 81 ,然後我再跟你說「低一點」,所以答案就一定會在 26 ~ 80 之間,就像下圖一樣,紅色區域是有可能的答案,而黑色區域是已經被排除的數字。

1
26
80
100

當你每次都猜最中間的數字(例如 1 ~ 100 中間是 50),就會將數字列表切成兩個一樣大的區塊,這個做法可以一次排除一半錯誤的數字,例如我們已經知道答案在 26 ~ 80 之間,那麼我下一次就可以猜 53 ( (26 + 80) / 2 ),若是我告訴你「再低一點」,那麼你就會知道答案在 26 ~ 52 之間。

1
26
53
100

我們來看看猜數字遊戲中的程式演算法,如果題目的答案是 1 ~ n 之間的數字,首先我們定義一個變數 min ,min 代表可能的答案中的最小值,再定義一個變數 max , max 代表可能的答案中的最大值。

演算法邏輯 如下:

1. 設定 min = 1,以及 max = n.
2. 取 min ~ max 的中間值 m。
3. 如果 m 是答案,那麼程式就可以回值傳,
4. 如果 m 小於答案,那麼設定 min = m + 1,回到第 2 步
4. 如果 m 大於答案,那麼設定 max = m - 1,回到第 2 步

實作陣列的 Binary Search

來試看看如果在一個已排序的 Array 中使用 Binary Search ,首先我們有 25 個由小到大排序過的質數如下。

var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];

假設我們想知道 67 是否為質數,這時只要在 primes 這個變數中搜尋看看是否存在 67 ,若是有在 Array 中找到 67 的 index ,那麼就可以得知 67 是質數。

如果我們從 Array 最左邊開始尋找,那麼我們要比對 18 次,才能找到 67 ,這個搜尋方式是很普通的 linear search 。


Binary Search 會是一個更有效率的搜尋方式,這個 Array 中含有 25 個數字,Index 分別是從 0 ~ 24 ,使用上述所講的演算法邏輯來猜數字。

1. 設定 min = 0, max = 24
2. 取得 index = 12 的值, number = 41
3. 41 < 67 , 設定 min = 13
4. 取得 index = 18, number = 61
5. 存在 61 ,所以 61 是質數

我們總共只猜了兩次,第一次猜 index 12 , 第二次猜 index 18 ,就猜中了答案,這個搜尋方式遠比 Linear search 快得多。

Binary Search source code

JavaScript: Binary Search
  1. function binarySearch(array, targetValue) {
  2. var min = 0, max = array.length - 1, guess, value;
  3. while(1) {
  4. if (max < min) break;
  5. guess = Math.floor((min + max)/2);
  6. value = array[guess];
  7. if (value === targetValue) {
  8. return guess;
  9. } else if (value > targetValue) {
  10. max = guess - 1;
  11. } else if (value < targetValue) {
  12. min = guess + 1;
  13. }
  14. }
  15. return -1;
  16. };
  17.  
  18. var primes = [
  19. 2, 3, 5, 7, 11,
  20. 13, 17, 19, 23, 29,
  21. 31, 37, 41, 43, 47,
  22. 53, 59, 61, 67, 71,
  23. 73, 79, 83, 89, 97];
  24.  
  25. var result = binarySearch(primes, 73);
  26. console.log(result);

相關文章


回應 (Leave a comment)