3–2 二元搜尋 Binary Search
前面我們已經提到二元搜尋與線性搜尋的不同。
而二元搜尋又是怎麼執行的呢?首先,針對這個已排序陣列中“正中央”的數據,進行與目標數據的比較,本次比較結果(大於,小於,或等於)就可以告訴我們,目標數據是在中央數據的前方或後方,相當於刪去了一半的搜尋範圍。接著再從留下來的那一半中繼續進行二元搜尋,直到找到目標 (中央數據等於目標數據),或是確認目標在此陣列中不存在。
二元搜尋的執行時間可以理解為這個陣列可以被對半切割的次數,即是O(log n)。
線性搜尋 v.s. 二元搜尋
以速度來說,二元搜尋 O(log n) 優於線性搜尋 O(n),二元搜尋的速度會是線性搜尋的“指數”倍。(如果 x = log2(n), 則 n = 2^x)
但因為二元搜尋僅適用於已排列好的陣列,因此陣列的維護比較麻煩,每次新增數據都要插入正確的位置,保持陣列的排序。而線性搜尋就沒有這種困擾,新增數據時可以加在陣列最後方即可。
綜合以上針對執行時間和陣列維護的比較,我們在選擇使用哪種陣列儲存方式搭配搜尋方式時,應該思考我們之後是否會頻繁地在此陣列中新增數據 (較適合用線性搜尋),或是較頻繁地搜尋數據 (這時就比較適合二元搜尋)。