iT邦幫忙

2021 iThome 鐵人賽

DAY 2
0
自我挑戰組

30天不怕演算法:白話文版系列 第 2

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次的時候找到那個字。

上一篇
Day 01:什麼是演算法?
下一篇
Day 03:如何分析演算法?
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言