这里所称的搜索(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(\log \log 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}}# 复杂度参考图表

Big-O 复杂度参考图表