简述简单实现简单二分搜索 ?
参考答案:
二分搜索(也称为二分查找)是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是目标值,则搜索过程结束;如果目标值大于或小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
以下是一个简单的二分搜索的Python实现:
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid
if guess > target:
high = mid - 1
else:
low = mid + 1
return None
# 测试
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # 输出: 1
print(binary_search(my_list, -1)) # 输出: None
这个函数接受一个有序数组(arr
)和一个目标值(target
)作为参数。然后,它初始化两个指针,一个指向数组的开始(low
),另一个指向数组的结束(high
)。在每一步中,它计算中间索引(mid
),然后检查该索引处的值(guess
)是否等于目标值。如果是,函数返回该索引。如果guess
大于target
,则目标值必须在数组的左半部分,因此将high
设置为mid - 1
。否则,目标值必须在数组的右半部分,因此将low
设置为mid + 1
。如果low
大于high
,则说明数组中不存在目标值,函数返回None
。
学习笔记
0 学习笔记