数组的搜索算法有哪些？

数组搜索算法大全：线性搜索：遍历数组，时间复杂度 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中文网其他相关文章！