python二分查找算法
时间: 2023-07-10 19:28:50 浏览: 61
二分查找算法,也称折半查找算法,是一种高效的查找算法。其基本思想是将查找区间逐步缩小,每次将查找区间的中间元素与目标元素进行比较,如果中间元素大于目标元素,则在左半部分继续查找,否则在右半部分继续查找,直到找到目标元素或者查找区间为空。下面是 Python 二分查找算法的实现:
```python
def binary_search(arr, target):
low, high = 0, 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` 为 `mid + 1`;否则,目标元素在左半部分,更新右边界 `high` 为 `mid - 1`。不断重复上述过程,直到找到目标元素或者查找区间为空,此时返回 -1 表示未找到目标元素。
例如,对于有序数组 `[1, 2, 3, 4, 5]`,如果要查找元素 4,可以调用 `binary_search` 函数进行查找,返回结果为 3,即目标元素 4 的下标为 3。