用Python实现一个二分查找的函数?
参考答案:
二分查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是目标值,则搜索过程结束;如果目标值大于或小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
以下是一个用Python实现的二分查找函数:
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
# 如果 mid 元素 < x,忽略左半部分
if arr[mid] < x:
low = mid + 1
# 如果 mid 元素 > x,忽略右半部分
elif arr[mid] > x:
high = mid - 1
# mid 元素 == x,返回 mid
else:
return mid
# x 不存在于 arr 中
return -1
# 测试数组
arr = [2, 3, 4, 10, 40]
x = 10
# 函数调用
result = binary_search(arr, x)
if result != -1:
print("元素在数组中的索引为", str(result))
else:
print("元素不在数组中")
在这个函数中,arr
是要进行搜索的有序数组,x
是要查找的元素。如果元素在数组中,函数将返回元素的索引;如果元素不在数组中,函数将返回 -1。