【Python】linear search 線性搜尋｜演算法介紹、新手快速入門

基本概念

線性搜尋（Linear Search），又稱為順序搜尋，是一種基本的搜尋演算法，用於在一個資料集合（通常是一個陣列或串列）中尋找特定元素的位置或值。其基本概念如下：

步驟：

從資料集合的第一個元素開始，逐一檢查每個元素，直到找到目標元素或搜索完整個集合。
對比目前檢查的元素與目標元素是否相等。如果相等，則表示找到了目標元素，並返回其位置（索引）。如果不相等，繼續檢查下一個元素。
如果搜尋完整個資料集合仍未找到目標元素，則返回一個特定的標記（例如-1），表示目標元素不存在於集合中。

特點：

線性搜尋是一種簡單而直觀的搜尋方法，適用於小型資料集合或未排序的資料。
它不要求資料集合是按任何特定順序排列的，因為它會逐一檢查每個元素。
時間複雜度為O(n)，其中n是資料集合中的元素數量。最壞情況下，需要搜索整個集合。
線性搜尋適用於資料量不大且搜尋操作不需要高
效率的情況。對於大型、排序過的資料集合，其他搜尋演算法如二分搜尋可能更為適合，因為它們可以在較快的時間內找到目標元素。

線性搜尋雖然簡單，但在某些情況下仍然非常有用，尤其是當資料集合較小或搜尋操作不需要高效率時。

實際應用

以下是使用 Python 實際運用線性搜尋的範例。

假設我們有一個包含數字的列表，我們想要找到特定的數字是否存在於列表中，以及它的索引位置（如果存在）。

def linear_search(arr, target):
     for i in range(len(arr)):
         if arr[i] == target:
             return i  # 找到目標，返回索引位置
     return -1  # 目標不存在於列表中，返回-1
 測試
 my_list = [5, 8, 2, 9, 12, 7, 4]
 target_number = 9

 result = linear_search(my_list, target_number)

 if result != -1:
     print(f"目標數字 {target_number} 存在於列表中，索引位置為 {result}")
 else:
     print(f"目標數字 {target_number} 不存在於列表中")

這個範例中，我們定義了一個名為 linear_search 的函數，它接受兩個參數：一個列表 arr 和一個目標數字 target。函數使用 for 迴圈逐一檢查列表中的元素，如果找到目標數字，則返回該數字在列表中的索引位置，否則返回 -1 表示目標數字不存在於列表中。

在測試部分，我們創建了一個列表 my_list 和一個目標數字 target_number，然後調用 linear_search 函數來尋找目標數字。

最後，我們根據返回值判斷目標數字是否存在於列表中，並顯示結果。

以上是簡單的線性搜尋實例，可以根據不同的需求和資料集合來使用這個演算法。如果資料量非常大或需要更高效率的搜尋，則可能需要考慮其他搜尋演算法。