二分搜尋演算法 (Binary search algorithm) - 終極密碼

圖片來源

終極密碼

再進入 Binary search 之前，先來玩一段小程式（可以點 這裏 試玩）：

import random

def guess_the_number(total_tries, start_range, end_range):
    if start_range > end_range:
        start_range, end_range = end_range, start_range
        
    random_number = random.randint(start_range, end_range)
    try_count = 0
    success_message = "答對了！！"
    failure_message = "遊戲結束！！"
    miss_message = "答錯囉！！"
    
    num_tries = 0
    while num_tries < total_tries:
        attempt = int(input("輸入數字: "))
        
        if attempt == random_number:
            print(success_message)
            return
        print(miss_message)
        if attempt < random_number:
            print("再高一點!")
        else:
            print("再低一點!")
        num_tries += 1
    print(failure_message)
    print(random_number)

total_tries = 5
start_range = 1
end_range = 100
guess_the_number(total_tries, start_range, end_range)

這其實就是以前常玩的猜數字（終極密碼）的遊戲。猜一個數字看是否正確，不正確的話是比正確數字大還是小，然後繼續猜另一半，雖然帶有一點隨機性，不過概念就跟 Binary search 相似。

但在再更進一步了解 Binary search 之前，先來了解一下 Linear search。

Linear search

假設有一本字典，我們要從字典裡面找到一個單字。但這本字典編輯的很爛，它並沒有按照字母順序排列，那我們該如何找到這個單字？

看起來我們只能從第一頁開始逐個字的看，直到找到為止。這就是 Linear search。

Linear search 的時間複雜度是多少？ O(n)

Binary search

因為上一本字典太爛，所以現在我們去買一本字母是按照順序排列的字典。那我們該如何找到這個單字？

一般來說（撇除我們知道字母在哪，從頭或是尾巴開始找），會先翻到中間，然後，我們會執行以下操作：

• 將目標單詞與該頁面上的單詞進行比較。
• 如果目標單字排在前面（按照字母順序），那麼我們將丟棄本書的右半部分。從現在開始，將只搜索左半部分。
• 同樣，如果該單字在本頁上的單字的後面，則我們將本書的左半部分丟棄。從現在開始，將只搜索右半部分。

如此一來，便可以確保在第一步時，就已經過濾掉一半的搜索空間，並重複以上步驟，就可以找到目標單字。這就是 Binary search 。

注意：在這裡 Binary 的意思是具有兩個部分，且 Binary search 的資料需要經過排序

總而言之 Binary search ：

• Binary search 是通過搜索中間值與目標值來進行比較來找到目標的位置。
• 若中間值等於目標值，即找到位置。
• 若目標值在中間值之前，則繼續找尋左半邊部分，反之則找尋右半部分。
• 重複上述步驟，直到找到目標值為止。

Efficiency of Binary Search

現在我們知道了 Binary Search 的運作原理，也知道了使用 Binary Search 的資料必須是經過排序的資料。那它的時間複雜度該如何計算？ 我們再來看一個範例，現在有一個經過排序的陣列如下：

data:   [1, 2, 4, 5, 6, 7, 8, 13, 14, 15, 16, 18]
index:   1  2  3  4  5  6  7  8   9   10  11  12

如果我現在要找16在 array 中的哪個位置，就開始從中間搜尋:

data:   [1, 2, 4, 5, 6, 7, 8, 13, 14, 15, 16, 18]
index:   1  2  3  4  5  6  7  8   9   10  11  12
                        ＾
                        mid

比對發現7<16，所以要繼續搜索 array 的右半邊。

data:   [8, 13, 14, 15, 16, 18]
index:   1  2   3   4   5   6 
                ＾
                mid

再比對發現14<16，所以要繼續搜索 array 的右半邊。

data:   [15, 16, 18]
index:   1   2   3 
             ＾
             mid

最後比對發現16=16，找到了目標值。

經過這個範例，一共比對了三次才找到16，就是對半分三次，即 1/2 * 1/2 * 1/2 = (1/2)^3。

全部有 12 個資料，所以是 12 * (1/2)^3 = 1，而現在可以做以下的運算：

step 0:

12 * (1/2)3 = 1

step 1: 若有 n 個元素，則要對半 k 次

n * (1/2)k = 1

step 2: 上面等於下面

n * 1/2k = 1

step 3: 同乘 2k

2k * n/2k = 2k

step 4: 變成

n = 2k

所以以 2 為底 n 的對數是 log2(n) = k， 所以 k 就是 log2(n)，也就是在最糟情況下，要從 n 個元素中搜尋到某一個元素，則要折半比對的次數為 k 次，就是 log2(n) 次。

Binary search 的時間複雜度是多少？ O(log n)

練習程式碼

可以到 clone github 的程式碼練習（01, 02），或是把程式碼複製到 online_python_compiler 練習也可以。

Resource

• 為什麼Binary Search 二元搜索法的時間複雜度是O(log(n))
• [演算法] Big O Notation & Time Complexity
• Udacity Data Structures and Algorithms Class

• ← Previous Post
• Next Post →