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