演算法圖鑑讀書筆記 — 第參章：陣列搜尋

3–1 線性搜尋 Linear Search

線性搜尋是從陣列中搜尋數據的演算法，和下一節要說明的“二元搜尋”不同，線性搜尋可以應用在散亂排序的數據，但二元搜尋僅能應用在已排列好的數據上。

線性搜尋的執行是從一個陣列的最前方開始，逐一比較是否與要搜尋的目標一致，如果一致則表示搜尋到目標，就可以結束搜尋。

因為是逐一由陣列的頭往後比較，所以執行時間會是O(n)。缺點是當搜尋目標在陣列的比較後方，或是目標根本不存在於此陣列時，就會非常耗費時間。

3–2 二元搜尋 Binary Search

前面我們已經提到二元搜尋與線性搜尋的不同。

而二元搜尋又是怎麼執行的呢？首先，針對這個已排序陣列中“正中央”的數據，進行與目標數據的比較，本次比較結果(大於，小於，或等於)就可以告訴我們，目標數據是在中央數據的前方或後方，相當於刪去了一半的搜尋範圍。接著再從留下來的那一半中繼續進行二元搜尋，直到找到目標 (中央數據等於目標數據)，或是確認目標在此陣列中不存在。

二元搜尋的執行時間可以理解為這個陣列可以被對半切割的次數，即是O(log n)。

線性搜尋 v.s. 二元搜尋

以速度來說，二元搜尋 O(log n) 優於線性搜尋 O(n)，二元搜尋的速度會是線性搜尋的“指數”倍。(如果 x = log2(n)， 則 n = 2^x)

但因為二元搜尋僅適用於已排列好的陣列，因此陣列的維護比較麻煩，每次新增數據都要插入正確的位置，保持陣列的排序。而線性搜尋就沒有這種困擾，新增數據時可以加在陣列最後方即可。

綜合以上針對執行時間和陣列維護的比較，我們在選擇使用哪種陣列儲存方式搭配搜尋方式時，應該思考我們之後是否會頻繁地在此陣列中新增數據 (較適合用線性搜尋)，或是較頻繁地搜尋數據 (這時就比較適合二元搜尋)。