二分查找python
时间: 2023-08-14 09:13:51 浏览: 97
二分查找(Binary Search)是一种常用的查找算法。它适用于已排序的数组或列表。下面是一个用Python实现二分查找的示例代码:
```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 = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
if result != -1:
print("元素在索引", result)
else:
print("元素不在数组中")
```
这段代码定义了一个 `binary_search` 函数,它接受一个已排序的数组 `arr` 和目标值 `target`。算法使用两个指针 `low` 和 `high` 分别表示当前查找范围的最低索引和最高索引。在每一次迭代中,算法计算中间索引 `mid`,并将目标值与中间元素进行比较。如果目标值等于中间元素,则返回该索引;如果目标值小于中间元素,则将最高索引更新为中间索引减一;如果目标值大于中间元素,则将最低索引更新为中间索引加一。如果循环结束后仍未找到目标值,则返回 -1。
在示例中,我们创建了一个已排序的数组 `[1, 3, 5, 7, 9]`,并且要查找的目标值是 `5`。调用 `binary_search` 函数后,返回索引 2,表示目标值在数组中的位置。
希望这个示例对你有帮助!如果你还有其他问题,请继续提问。
阅读全文