第一個演算法既是叫搜尋，那我們先想像一些生活中找東西的情境。

如果有一疊照座號排好的作業，要找出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次的時候找到那個字。