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

今天就到这边啦～明天见掰掰！