Binary Search

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

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

猜數字遊戲

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

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

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

演算法邏輯 如下：

實作陣列的 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 ，使用上述所講的演算法邏輯來猜數字。

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

Binary Search source code

function binarySearch(array, targetValue) {
    var min = 0, max = array.length - 1, guess, value;
    while(1) {
        if (max < min) break;
        guess = Math.floor((min + max)/2);
        value = array[guess];
        if (value === targetValue) {
            return guess;
        } else if (value > targetValue) {
            max = guess - 1;
        } else if (value < targetValue) {
            min = guess + 1;
        }
    }
    return -1;
};
 
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];
 
var result = binarySearch(primes, 73);                                                                                                           
console.log(result);

相關文章

• https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/binary-search