這裡所稱的搜尋(Search)，是指在一個已排序好或是尚未排序好的集合中，將指定元素的鍵值(key)或是索引值(index)搜尋出來，或者是給定某個條件，在集合中搜索出符合該條件的資料。在集合內搜尋元素的方法當然不會只有一種，而不同方法搜尋資料的難易度、速度和其它特性自然也會有所不同。搜尋演算法(Search Algorithm)就是搜尋資料的方法，目前已知的方法有很多，在這篇文章中將會整理本站所介紹過的大部份搜尋演算法。



一般搜尋演算法

這邊所列表出來的演算法都是用來搜尋某個已知的元素在集合中的位置。

以#{{n}}#來表示要搜尋的資料筆數。

演算法 最差時間複雜度 最佳時間複雜度 平均時間複雜度 最差空間複雜度 應用場合
線性搜尋
Linear Search		 #{{O(n)}}# #{{O(1)}}# #{{O(n)}}# #{{O(1)}}# 適用於任何集合。
二元搜尋
Binary Search		 #{{O(\log n)}}# #{{O(1)}}# #{{O(\log n)}}# 遞迴：#{{O(\log n)}}#
迭代：#{{O(1)}}#		 適用於已排序好的序列。
指數搜尋
Exponential Search		 #{{O(\log n)}}# #{{O(1)}}# #{{O(\log n)}}# 遞迴：#{{O(\log n)}}#
迭代：#{{O(1)}}#		 特別適用於已排序的序列長度很長，且要查找的元素位於序列較前端的位置時。
插補搜尋
Interpolation Search		 #{{O(n)}}# #{{O(1)}}# #{{O(n)}}# 遞迴：#{{O(n)}}#
迭代：#{{O(1)}}#		 特別適用於已排序的序列長度很長，且資料分佈平均時。
費式搜尋
Fibonacci Search		 #{{O(\log n)}}# #{{O(1)}}# #{{O(\log n)}}# #{{O(1)}}# 適用於已排序好的序列，且運行於不擅長處理乘、除法的處理器上。

特殊搜尋演算法

字串搜尋演算法

搜尋文字中與樣本相同的子字串位置。

以#{{n}}#來表示要搜尋的資料筆數。以#{{m}}#來表示要搜尋的樣本資料筆數。以#{{k}}#來表示要搜尋的資料可能的值的數量。

演算法 最差時間複雜度 最佳時間複雜度 平均時間複雜度 最差空間複雜度 應用場合
暴力字串搜尋
Brute-force Substring Search		 #{{O(nm)}}# #{{O(m)}}# ? #{{O(1)}}# 特別適用於短文字的搜索。
Boyer-Moore-MagicLen #{{O(m + k) + O(nm)}}# #{{O(m + k) + O({n \over m})}}# ? #{{O(m + k)}}# 特別適用於長文字的搜索。

樹或圖的搜尋演算法

以#{{v}}#來表示節點的數量。以#{{e}}#來表示邊的數量。

演算法 最差時間複雜度 最佳時間複雜度 平均時間複雜度 最差空間複雜度
深度優先搜尋
DFS		 #{{O(v + e)}}# #{{O(1)}}# #{{O(v + e)}}# #{{O(v)}}#
廣度優先搜尋
BFS		 #{{O(v + e)}}# #{{O(1)}}# #{{O(v + e)}}# #{{O(v)}}#

排名搜尋演算法

在序列中快速找出第#{{K}}#小或是第#{{K}}#大的元素。

以#{{n}}#來表示要搜尋或排序的資料筆數。

演算法 最差時間複雜度 最佳時間複雜度 平均時間複雜度 最差空間複雜度 是否穩定 應用場合
快速選擇
Quickselect		 #{{O(n^2)}}# #{{O(n)}}# #{{O(n)}}# #{{O(1)}}# 是 想從序列中找出一個第K小或是第K大元素時。

Big-#{{O}}# 複雜度參考圖表

algorithm