DSA 線性搜尋

線性搜尋

線性搜尋演算法透過陣列進行搜尋，並返回所搜尋值的索引。

執行上面的模擬，檢視線性搜尋演算法的工作原理。

要檢視值未找到時會發生什麼，請嘗試查詢值 5。

這種演算法非常簡單，易於理解和實現。

如果陣列已經排序，最好使用我們將在下一頁介紹的、速度快得多的二分搜尋演算法。

排序演算法和搜尋演算法之間的一個大區別是，排序演算法會修改陣列，而搜尋演算法會保持陣列不變。

手動演練

在實際用程式語言實現線性搜尋之前，我們先手動嘗試一下，以便更好地理解其工作原理。我們將搜尋值 11。

第一步： 我們從一個隨機值陣列開始。

第二步： 我們檢視陣列中的第一個值，它是否等於 11？

第三步： 我們移動到索引 1 處的下一個值，並將其與 11 進行比較，看它們是否相等。

第四步： 我們檢查索引 2 處的下一個值。

第五步： 我們移動到索引 3 處的下一個值。它是否等於 11？

我們找到了！

值 11 在索引 3 處找到。

返回索引位置 3。

線性搜尋完成。

執行下面的模擬，以動畫形式檢視以上步驟。

手動執行：發生了什麼？

這個演算法非常直接。

從陣列開頭開始檢查每個值，看該值是否等於 11（我們要查詢的值）。

找到該值後，搜尋停止，並返回找到該值的索引。

如果遍歷整個陣列都沒有找到該值，則返回 -1。

線性搜尋實現

要實現線性搜尋演算法，我們需要

1. 一個包含要搜尋值的陣列。
2. 要搜尋的目標值。
3. 一個從頭到尾遍歷陣列的迴圈。
4. 一個 if 語句，用於比較當前值與目標值，如果找到目標值，則返回當前索引。
5. 迴圈結束後，返回 -1，因為此時我們知道目標值未找到。

線性搜尋的結果程式碼如下所示：

def linearSearch(arr, targetVal):
    for i in range(len(arr)):
        if arr[i] == targetVal:
            return i
    return -1

arr = [3, 7, 2, 9, 5]
targetVal = 9

result = linearSearch(arr, targetVal)

if result != -1:
    print("Value",targetVal,"found at index",result)
else:
    print("Value",targetVal,"not found")

線性搜尋時間複雜度

有關時間複雜度的一般性解釋，請訪問此頁面。

有關插入排序時間複雜度的更全面、詳細的解釋，請訪問 此頁面。

如果線性搜尋執行並找到目標值，並且目標值是 \(n\) 個值的陣列中的第一個陣列值，則只需要一次比較。

但是，如果線性搜尋遍歷完 \(n\) 個值的整個陣列而沒有找到目標值，則需要 \(n\) 次比較。

這意味著線性搜尋的時間複雜度為：

\[ O(n) \]

如果我們繪製線性搜尋在 \(n\) 個值的陣列中查詢值所需的時間圖，我們會得到這張圖：

執行下面的模擬，嘗試不同的陣列大小，看看線性搜尋需要多少次比較才能在 \(n\) 個值的陣列中找到一個值。

在上面的模擬中選擇“隨機”、“降序”或“升序”對線性搜尋的速度沒有影響。

def linearSearch(arr, targetVal):
    for i in range(len(arr)):
        if arr[i] == targetVal:
          
    return -1