Table of Contents
前言
一連講了好幾個Sorting的演算法，我們今天來換換口味，今天要講的演算法是用來針對已經排序之後的陣列進行搜尋，一個也很容易理解的演算 - Binary Search。
Binary Search的運行過程
Binary Search的基本概念是將已經排序的陣列用二分法拆成左右兩半進行比較，因為是已經排序的陣列，所以知道拆分過後的兩半，左邊比較小，右邊比較大，進而快速篩選出目標可能在哪一個部分，因此流程如下：
- 從一個已經正序排列的陣列中，直接取
中間位置的值與目標（Ｋ）進行比較。 - 經過上述比較，會有三種可能：
- 陣列正中間位置的值
等於Ｋ，則找到目標。 - 陣列正中間位置的值
小於Ｋ，則表示Ｋ位於右邊區段。 - 陣列正中間位置的值
大於Ｋ，則表示Ｋ位於左邊區段。
- 陣列正中間位置的值
- 此時已經Ｋ可能的所屬區段，再針對該區段進行第一步，反覆直到找到Ｋ的位置。（當然也有可能全部找完找不到Ｋ）
看看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是一樣的：
- 將這堆金幣依照數量平均分成兩邊，拿去秤重。
- 找出比較輕的一方，即表示假金幣在其中。
- 再將這一方的金幣依照數量平均分成兩堆，再拿去秤重。
- 一樣，較輕的一方為假金幣所在的地方。
- 重複上述步驟，直到假金幣現出原形。
這種解決辦法就是Binary Search的一個應用。
小結
- Binary Search只能用在
已經排序的陣列上。 - Binary Search的時間複雜度為
𝜪(㏒2 n)。 - 尋找假金幣的方式就是透過Binary Search來進行。
預告
明天我們將會介紹一種資料結構 - Binary Search Tree。