数组搜索算法大全：线性搜索：遍历数组，时间复杂度 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 
