本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

一連講了好幾個Sorting的演算法，我們今天來換換口味，今天要講的演算法是用來針對已經排序之後的陣列進行搜尋，一個也很容易理解的演算 - Binary Search。

Binary Search的運行過程

Binary Search的基本概念是將已經排序的陣列用二分法拆成左右兩半進行比較，因為是已經排序的陣列，所以知道拆分過後的兩半，左邊比較小，右邊比較大，進而快速篩選出目標可能在哪一個部分，因此流程如下：

1. 從一個已經正序排列的陣列中，直接取中間位置的值與目標（Ｋ）進行比較。
2. 經過上述比較，會有三種可能：
   • 陣列正中間位置的值等於Ｋ，則找到目標。
   • 陣列正中間位置的值小於Ｋ，則表示Ｋ位於右邊區段。
   • 陣列正中間位置的值大於Ｋ，則表示Ｋ位於左邊區段。
3. 此時已經Ｋ可能的所屬區段，再針對該區段進行第一步，反覆直到找到Ｋ的位置。（當然也有可能全部找完找不到Ｋ）

看看GIF吧：

有一個點特別提出來說明，所謂的『中間位置』，其實算法是將頭尾兩個位置所屬的index值相加後除以2，在無條件捨去而決定的，因此在上方GIF中，當只剩下四個位置的值要比較時，就是透過這個方式選擇20來進行比較，而非24。

那Binary Search的Pseudo-code大概會是怎樣呢？

// Input: An array Array[l,...,r] of ordered elements, and a search target k
// Output: an index to the position of k in Array if k is found or -1 otherwise.
function BinarySearchRecursive(Array[l,...,r], k){
    if l > r {
        return -1;
    }
    m = round((l+r)/2);
    if k = Array[m] {
        return m;
    }else if k < Array[m]{
        return BinarySearchRecursive(Array[l,...,m-1], k);
    }else{
        return BinarySearchRecursive(Array[m+1,...,l], k);
    }
}

這種在一個方法中再次呼叫自身方法的寫法稱為遞迴(Recursive)

Binary Search的時間複雜度

Binary Search在進行的過程中，每一次的迴圈都會將要搜尋的範圍減半，這個方式可以大幅降低執行時間，因此對於這種會將範圍砍半的演算法，基本上其時間複雜度皆為Ｏ(㏒2 n)。

真假硬幣的分辨

假設現在有一堆的金幣，而其中有一枚金幣是假的，目前已知假金幣比較輕，那我們要如何找出這一枚假金幣呢？

既然這個問題出現在這篇文章，就表示這個解決辦法與Binary Search是一樣的：

1. 將這堆金幣依照數量平均分成兩邊，拿去秤重。
2. 找出比較輕的一方，即表示假金幣在其中。
3. 再將這一方的金幣依照數量平均分成兩堆，再拿去秤重。
4. 一樣，較輕的一方為假金幣所在的地方。
5. 重複上述步驟，直到假金幣現出原形。

這種解決辦法就是Binary Search的一個應用。

小結

1. Binary Search只能用在已經排序的陣列上。
2. Binary Search的時間複雜度為Ｏ(㏒2 n)。
3. 尋找假金幣的方式就是透過Binary Search來進行。

預告

明天我們將會介紹一種資料結構 - Binary Search Tree。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin