Python:实现二分查找算法
时间: 2023-06-15 09:04:08 浏览: 76
二分查找算法也称为折半查找算法,是一种高效的查找算法。它的基本思想是:在有序数组中,通过将数组不断地对半分,找到目标元素的位置。
以下是 Python 代码实现:
```python
def binary_search(arr, target):
left = 0
right = 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 # 目标元素不存在
# 测试
arr = [1, 3, 5, 7, 9]
target = 5
print(binary_search(arr, target)) # 输出: 2
```
这里的 `arr` 表示有序数组,`target` 表示要查找的目标元素。`left` 和 `right` 分别表示数组的左边界和右边界。
在 `while` 循环中,我们计算出数组的中间位置 `mid`,如果 `arr[mid]` 等于 `target`,则直接返回 `mid`。如果 `arr[mid] < target`,则目标元素在右半部分,需要将左边界 `left` 赋值为 `mid + 1`。如果 `arr[mid] > target`,则目标元素在左半部分,需要将右边界 `right` 赋值为 `mid - 1`。如果 `while` 循环结束后仍然没有找到目标元素,则返回 `-1` 表示目标元素不存在。
以上是二分查找算法的 Python 实现。