二分查找(Binary Search)是一种常见且高效的查找算法。它要求在已排序的元素序列中找到目标值。
迭代(Iterative)方法是一种通过迭代循环来实现功能的方法。下面是Python中二分查找的迭代方法:
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
该函数接受两个参数,分别是已排序数组arr和目标值target。变量low和high分别存储当前查找区间的左右端点。mid等于low和high的中间位置。如果mid等于target,则返回mid。如果mid小于target,则更新low为mid+1。如果mid大于target,则更新high为mid-1。如果最终未找到target,则返回-1表示查找失败。
该函数的时间复杂度为$O(log_2n)$。