《演算法圖鑑》第三章：陣列搜尋
Published in
4 min readJan 26, 2019
介紹《演算法圖鑑》第二章：排序 時有提及線性搜尋 ( Linear Serch )，第三章就是在介紹從陣列中搜尋資料的演算法。以下依據書上所列的線性搜尋 ( Linear Search ) 和二元搜尋 ( Binary Search ) 做整理。
線性搜尋 ( Linear Search )
- 線性搜尋 ( Linear Serch ) 是從陣列中搜尋資料的演算法，從陣列前端開始依序往後查詢資料，直到搜尋到指定資料時才停止搜尋。也稱作循序搜尋 ( Sequential Search )。
線性搜尋要多少執行時間？
因為線性搜尋是從頭依序比較，當數據量大且搜尋目標在陣列後方，或搜尋目標並不存在於陣列中時，比較次數會變多且耗時。
當資料量為 n 時，執行時間為 O(n)。
二元搜尋 ( Binary Search )
- 二元搜尋 ( Binary Search ) 是從陣列中搜尋資料的演算法，只適用於有序陣列 ( 資料已排序完成的陣列 )。將搜尋的目標與陣列正中央的資料做比較，進而判斷搜尋目標在陣列正中央資料之前 ( 左側 ) 或之後( 右側 )，一直到搜尋範圍只剩一個資料時結束搜尋。也稱作折半搜 ( Half-Interval Search ) 或對數搜尋 ( Logarithmic Search )。
- 每比較一次搜尋目標與陣列中央的資料，就會縮小一半的搜尋範圍。
二元搜尋要多少執行時間？
因為二元搜尋是使用有排序過的陣列，可以讓每次搜尋的範圍減半，直到搜尋範圍只剩一個資料時結束搜尋。
當資料量為 n 時，反覆進行每次減半的操作 log2(n)次後，資料剩下一個。所以二元搜尋進行 log2(n) 次「和陣列正中央的資料比較，使搜尋範圍減半」的操作後，就能搜尋到目標資料，若目標資料不存在，也能得出該目標資料不存在的結論。
所以執行時間是 O(log n)，為線性搜尋執行時間的指數倍。
