数组搜索算法大全:线性搜索:遍历数组,时间复杂度 o(n)。二分搜索(仅限有序数组):将数组二分,时间复杂度 o(log n)。哈希表:使用键值快速查找,时间复杂度 o(1)。
数组搜索算法大全
在计算机科学中,数组搜索算法用于在有序或无序数组中找到特定元素。本文将探讨各种数组搜索算法,包括其时间复杂度和实战案例。
线性搜索
时间复杂度: O(n)
线性搜索是最简单、最直接的搜索算法。它从数组的开头开始,并逐个比较元素,直到找到目标元素或到达数组的末尾。
python</a>;toolbar:false;'>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