Python 中的線性搜索

Python 是最流行和最強大的語言之一。執行代碼只需要幾行，這使得它成為用戶友好的語言。在本教程中，我們將學習 Python 中的線性搜索。搜索是一種查找特定元素在給定列表中是否存在的技術。

有兩種搜索方式-

• 線性搜索
• 二進位檢索

這兩種技術都廣泛用於搜索給定列表中的元素。

什麼是線性搜索？

線性搜索是一種在列表中查找元素的方法。這也稱為順序搜索。這是最簡單的搜索演算法，因為它以順序的方式搜索所需的元素。

它將每個元素與我們正在搜索的值進行比較。如果兩者都匹配，則找到元素，演算法返回鍵的索引位置。

線性搜索的概念

讓我們理解以下步驟，在給定的列表中找到元素 key = 7。

步驟- 1: 從第一個元素開始搜索，對列表 x 的每個元素檢查鍵= 7。

步驟- 2: 如果找到元素，返回鍵的索引位置。

步驟 3: 如果沒有找到元素，返回元素不存在。

線性搜索演算法

有一個要搜索的 n 元素和鍵值的列表。

下面是線性搜索演算法。

LinearSearch(list, key)
  for each item in the list
    if item == value
      return its index position
   return -1

Python 程序

讓我們理解下麵線性搜索演算法的 Python 實現。

程序

def linear_Search(list1, n, key):

    # Searching list1 sequentially
    for i in range(0, n):
        if (list1[i] == key):
            return i
    return -1

list1 = [1 ,3, 5, 4, 7, 9]
key = 7

n = len(list1)
res = linear_Search(list1, n, key)
if(res == -1):
    print("Element not found")
else:
    print("Element found at index: ", res)

輸出:

Element found at index:  4

說明:

在上面的代碼中，我們創建了一個函數 linear_Search()，，它採用三個參數——list 1、列表長度和要搜索的數字。我們為循環定義并迭代每個元素，並與鍵值進行比較。如果找到元素，返回 index else return -1，這意味著元素不在列表中。

線性搜索複雜性

線性搜索演算法的時間複雜度-

• 基本案例-0(1)
• 平均案例- O(n)
• 最壞情況-O(n)

線性搜索演算法適用於較小的列表(< 100)，因為它檢查每個元素以獲得所需的數量。假設有 10，000 個元素列表，並且期望的元素在最後一個位置可用，通過與列表中的每個元素進行比較，這將消耗大量時間。

為了得到快速的結果，我們可以使用二分搜索演算法。

我們已經討論了線性搜索的基本概念。在下一個教程中，我們將學習第二個也是最流行的搜索演算法二分搜索。