Aloha！又是我少女人妻 Uerica！最近發現寫鐵人賽文章不但可以學習知識，還能訓練自己如何當時間管理大師，像我這種愛睡愛做夢的真是一大挑戰啊～昨天還夢到自己把文章都寫完了，起床發現果然是"做夢"，哈哈哈555...

搜尋 Search 演算法

搜尋也是一般在網站或系統上常見的，簡單來說就是在資料中找出特定的資料，比對並輸出給使用者的操作方法，最常用在陣列資料結構中。

根據資料量的大小，搜尋可分為：

• 內部搜尋：資料量小，可從主記憶儲存中操作和找尋所要的資料。
• 外部搜尋：資料量大，需從外部記憶中找尋所要的資訊。因外部記憶體的操作較費時間，故需考慮如何減少存取時間與次數。

常見的搜尋演算法

線性搜尋法 Linear Search

線性搜尋法，又稱為循序搜尋 sequential search ，可用在搜尋未排序元素數列，執行方式是從頭開始依序走訪元素，直到找到該目標或走訪結束為止。此搜尋法雖然直覺，但只適合用在數列中元素不多的情況下，若需走訪的元素過多，則是效能較差的搜尋法。

線性搜尋法 Linear Search 操作圖解

• 取一個未排序數列，假設搜尋目標是元素 33。
  

• 從左邊開始一個個走訪
  
  

• 直到搜尋到目標為止，搜尋就完成了。
  

線性搜尋法 Linear Search 時間、空間複雜度

線性搜尋因為是從頭開始一個個走訪直到結束，因此如果要找的資料在最後方或目標不存在，比較次數就會根據資料大小而增加。

• 時間複雜度: 最佳: O(1)、最差: O(n)、平均: O(n)
• 空間複雜度為: O(1)

二分搜尋法 Binary Search

二分搜尋法只適合用在搜尋排序過的數列，執行方式是從中取一元素與搜尋目標做比對，若該元素大於搜尋目標，代表搜尋目標在該元素的左邊，再把剩餘的數列取中間元素與搜尋目標比對，反覆操作直到找到搜尋目標為止。

二分搜尋法 Binary Search 操作圖解

• 取一個已排序數列，搜尋目標是元素 33。
  

• 取數列中間的數來做比對，數列若無法切分為二則取接近的元素。下圖取中間偏左的元素 20 。
  

• 因元素 20 小於 33 ，所以小於元素 20 的值，包括元素 20 本身都可撇除。
  

• 從剩餘的元素再取中間值來比對，下圖取中間偏左的元素 49。
  

• 因 33 小於 49 ，所以大於 49 的元素，包括 49 本身都可撇除。
  

• 剩下 33 ，比對找到搜尋目標，搜尋完成。
  

二分搜尋法 Binary Search 時間、空間複雜度

每次判斷都會縮小一半的搜尋範圍，所以執行時間用對數表示。

• 時間複雜度: 最佳: O(1)、最差: O(log n)、平均: O(log n)
• 空間複雜度為: O(1)

二分搜尋與線性搜尋相比，速度是線性搜尋的指數倍，但使用二分搜尋的前提下，陣列必須先排序過。

參考資料

寫程式的基本功：搜尋演算法(Search Algorithm)

JavaScript 學演算法（二十）- 搜尋演算法

Rust Algorithm Club

今天就到這邊啦～明天見掰掰！