Day 02：二分搜寻(binary search)

第一个演算法既是叫搜寻，那我们先想像一些生活中找东西的情境。

如果有一叠照座号排好的作业，要找出28号同学的，我们很可能会先拿开上面半叠，从中间开始找。

或者如果要在一本英文字典里查一个m开头的字，大部分人会直接翻开中间，再看m应该往前翻或往後翻。

又或者，今天要在某通讯软件的朋友列表中找到一个姓张的朋友，不管列表是用笔画或注音排，我们应该会先一口气滑到中间左右再开始找。

为什麽上面这些事会这麽做呢？你可能会说：这样比较快啊！
其实这样的想法代表你已经掌握了一个演算法：二分搜寻(binary search)。

定时炸弹

小时候有个叫做定时炸弹的游戏，出题者心里先想好1-100的一个数字，猜的人猜到就算引爆炸弹输了。

假设现在稍微改一下规则，变成猜到的人赢，所以越快猜到越好。

如果毛豆同学猜1，出题者说太低，毛豆再猜2，出题者说太低，毛豆再猜3，出题者说太低...没猜多久毛豆一定会被笑笨，因为他一次只排除一个数字，假如出题者的数字在很後面，代表他最多要猜到快100次才会中。

这种方法叫做线性搜寻(linear search)，代表逐一检查每个项目，直到找到为止。

如果毛豆换一种方式，一开始猜50，出题者说太低，接着他再猜75，出题者说太高...这样的话要猜几次呢？

以这样的猜法，第一次猜完太低，等於1-49都不用再考虑，第二次太高，於是又排除了76-100。
以每猜一次排除的数字来看：

原本有100个数字 → 50 → 25 → 13 → 7 → 4 → 2 → 1

也就是说，如果每次都猜剩下数字的中间，每次都可以排除掉剩下数字的一半。这样排除7次就会只剩下1个数字，代表无论出题者心想任何数字，这种猜法最多都只要7次就可以猜中(是否瞬间觉得赢面变很大？)。这种方式就叫做二分搜寻(binary search)。

拿两个演算法相比来看，假设总数不一定是100，以任意n个项目来说，线性搜寻最多需要进行n个步骤，而二分搜寻最多只需要log2 n个步骤。[注1]

不过看到这里，你可能也发现了二分搜寻的一个条件：只有在所有数字或元素是有排序的情况下才能使用二分搜寻。可以试想，如果一本字典并不是从a-z排而是随便乱跳，那使用二分搜寻也无法比较快找到字。

程序中的搜寻

搜寻(searching)是寻找特定值的方法。就像我们几乎每天都在搜寻引擎上搜寻资料，同样也是输入值後得到结果，各种搜寻是程序中常见的任务。

在程序中，线性搜寻的输入(input)可以是任意阵列，而输出(output)可以是布林值，表示特定值是否在阵列中。例如有一阵列[3, 6, 1, 7, 2, 4, 0]，如果想知道7是否在其中，可以使用线性搜寻。

简单的程序码可写成如下(这里是javascript但也可以是任何语言)：

let ary = [3, 6, 1, 7, 2, 4, 5];
for (let i == 0; i < ary.length; i++){
    if(ary[i] == 7){
        return true;
    }
    return false;
}

如果是二分搜寻，输入就是一个有序阵列(sorted array)，如果搜寻的特定值有在阵列中，可以回传布林值，或者也可以回传该值在阵列中的位置。

二分搜寻的步骤大致如下：

1. 检查阵列的中间元素
2. 如果与目标相等，回传该位置
3. 如果目标小於该元素，继续在阵列前半部分搜寻(回到步骤1)
4. 如果目标大於该元素，继续在阵列後半部分搜寻(回到步骤1)

let binarySearch = function (arr, x) {
    let low = 0, high = arr.length-1; 
    while (low <= high){
        let mid = Math.floor((low + high)/2);
        // 如果目标元素在中间，回传位置
        if (arr[mid] === x){
            return mid;
        }
        // 否则搜寻前半或後半
        else if (arr[mid] < x){
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return false;
}
binarySearch([1, 3, 5, 7, 9], 7);

目前我们看到两种不同的搜寻演算法，接下来就要来讨论该如何比较或分析这些方法。

• [注1]如果你跟我一样差一点忘记对数(logarithm)，可以稍微想一下指数：
  2^10 = 1024 代表2乘2乘2...总共乘了10次，答案为1024
  log2 1024 = 10 就代表1024除2除2除2...总共除了10次会除完
  所以当我们说用二分搜寻找一个单字最多需要log2 n步骤，就好比一本1024页的字典，每次翻到中间(除2)，再翻到剩下的中间(除2)...最多会在翻10次的时候找到那个字。