線性搜尋(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

linear-search

線性搜尋法的程式實作

線性搜尋法的複雜度

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

項目 備註
最差時間複雜度 #{{O(n)}}# 直到走訪到最後一個元素才找到,或是元素根本不在該集合中。
最佳時間複雜度 #{{O(1)}}# 第一個走訪到的元素就是我們想找的元素。
平均時間複雜度 #{{O(n)}}#
最差空間複雜度 #{{O(1)}}#