给定一个有序序列,使用二分查找指定的值
时间: 2024-01-24 17:04:09 浏览: 80
数据结构笔记:二分查找
二分查找是一种高效的查找算法,它的时间复杂度为 O(log n)。下面是一个使用二分查找在有序序列中查找指定值的 Python 代码实现:
```python
def binary_search(arr, target):
left, right = 0, 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 和一个要查找的目标值 target。函数首先使用 left 和 right 两个变量分别指向序列的第一个和最后一个元素的位置。接着,使用 while 循环不断缩小查找范围,直到找到目标值或者查找范围为空。在每次循环中,计算中间元素的索引 mid,并将其与目标值进行比较,如果 mid 索引对应的元素等于目标值,则返回 mid;否则根据 mid 索引对应的元素与目标值的大小关系,缩小查找范围,继续进行下一轮循环。如果最终没有找到目标值,则返回 -1。
使用以上代码查找有序序列 [1, 3, 5, 7, 9] 中的元素 5,可以如下调用:
```python
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
print(result) # 输出 2
```
以上代码输出 2,表示目标值 5 在序列中的索引为 2。
阅读全文