线性搜索(Linear Search)算法又称为循序搜索(Sequential Search)算法,是学习编程语言最先需要学会的搜索算法。它可以按照元素在集合中的顺序,从头开始进行走访,并连续判断目前走访到的元素是否是我们想要找的元素。

线性搜索法(Linear Search)

线性搜索法的概念

线性搜索法是以土法炼钢的方式走访集合中的每个元素,并在每次迭代时去判断目前走访到的元素是否正是我们想要找的元素。

线性搜索法在任何场合下都可以使用,不需要去在乎集合中的元素顺序。然而虽然它直觉又方便,但它通常不会是一个很有效率的搜索方法。

线性搜索法的过程

前面有提到线性搜索法可以用在任何场合,这边就以无排序的整数数组来举例吧!假设现在有个整数数组,内容如下:

索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3

若要用线性搜索法来找到元素 6,那就从数组的索引 0 开始,判断索引 0 的元素是否是 6,如果不是的话就继续判断下一个索引的元素值。直到找到我们要找的元素值,也就是 6 后才停止。如果已经走访到数组结尾了,却都没有发现元素值 6 的话,表示 6 并不存在于这个数组之中。

       ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
     6 != 9

           ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
         6 != 8

               ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
             6 != 3

                   ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
                 6 != 3

                       ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
                     6 != 9

                           ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
                         6 != 2

                               ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
                             6 != 4

                                   ●
索引    0   1   2   3   4   5   6   7   8
数值    9   8   3   3   9   2   4   6   3
                                 6 == 6

线性搜索的过程动画

线性搜索法的程序实作

线性搜索法的复杂度

以 #{{n}}# 来表示要搜索的数据笔数。

项目 值 备注
最差时间复杂度 #{{O(n)}}# 直到走访到最后一个元素才找到,或是元素根本不在该集合中。
最佳时间复杂度 #{{O(1)}}# 第一个走访到的元素就是我们想找的元素。
平均时间复杂度 #{{O(n)}}#
最差空间复杂度 #{{O(1)}}#