iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 12
0
Software Development

舌尖上的演算法系列 第 12

Day12 -- Decrease and Conquer - Binary Search

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

前言

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


Binary Search的運行過程

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

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

看看GIF吧:

Binary Search

有一個點特別提出來說明,所謂的『中間位置』,其實算法是將頭尾兩個位置所屬的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在進行的過程中,每一次的迴圈都會將要搜尋的範圍減半,這個方式可以大幅降低執行時間,因此對於這種會將範圍砍半的演算法,基本上其時間複雜度皆為O(㏒2 n)


真假硬幣的分辨

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

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

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

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


小結

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

預告

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


References

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

上一篇
Day11 -- Decrease and Conquer - Shell Sort
下一篇
Day13 -- Decrease and Conquer - Binary Search Tree(上)
系列文
舌尖上的演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言