數組的搜尋演算法有哪些？

陣列搜尋演算法大全：線性搜尋：遍歷數組，時間複雜度 O(n)。二分搜尋（僅限有序數組）：將數組二分，時間複雜度 O(log n)。哈希表：使用鍵值快速查找，時間複雜度 O(1)。

陣列搜尋演算法大全

在電腦科學中，陣列搜尋演算法用於在有序或無序陣列中找到特定元素。本文將探討各種陣列搜尋演算法，包括其時間複雜度和實戰案例。

線性搜尋

時間複雜度： O(n)

線性搜尋是最簡單、最直接的搜尋演算法。它從數組的開頭開始，並逐一比較元素，直到找到目標元素或到達數組的末尾。

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

二分搜尋

時間複雜度： O(log n)

二分搜尋用於在有序數組中搜尋。它透過重複將數組分成兩半來縮小搜尋範圍。

def binary_search(arr, target):
  left, right = 0, len(arr) - 1
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
      return mid
    elif arr[mid] < target:
      left = mid + 1
    else:
      right = mid - 1
  return -1

哈希表

時間複雜度： O(1)

哈希表是一種資料結構，它允許我們通過鍵值快速查找元素。數組可以用作哈希表的底層資料結構，其中索引用作鍵。

def hash_search(arr, target):
  hash_table = {}
  for i in range(len(arr)):
    hash_table[arr[i]] = i
  if target in hash_table:
    return hash_table[target]
  else:
    return -1

實戰案例

考慮以下查找學生分數的陣列搜尋案例：

students = [
  {'name': 'John Doe', 'score': 85},
  {'name': 'Jane Doe', 'score': 90},
  {'name': 'Bill Smith', 'score': 75},
  {'name': 'Alice Johnson', 'score': 95}
]

如果我們想找到"Alice Johnson" 的分數，我們可以使用線性搜尋：

for student in students:
  if student['name'] == 'Alice Johnson':
    print(student['score'])  # 输出：95

或者，如果陣列按名稱排序，我們可以使用二分搜尋：

students.sort(key=lambda x: x['name'])

left, right = 0, len(students) - 1
while left <= right:
  mid = (left + right) // 2
  if students[mid]['name'] == 'Alice Johnson':
    print(students[mid]['score'])  # 输出：95
    break
  elif students[mid]['name'] < 'Alice Johnson':
    left = mid + 1
  else:
    right = mid - 1

以上是數組的搜尋演算法有哪些？的詳細內容。更多資訊請關注PHP中文網其他相關文章！