用递归的方法,给定一个有序序列,使用二分查找指定的值。
时间: 2024-02-06 16:09:48 浏览: 78
第六课_二分查找与二叉查找树.pdf
二分查找是一种高效的查找算法,它可以在有序序列中查找指定值。下面是使用递归方式实现的二分查找算法:
```python
def binary_search_recursive(arr, low, high, target):
"""
:param arr: 有序序列
:param low: 序列起始下标
:param high: 序列终止下标
:param target: 要查找的目标值
:return: 目标值在序列中的下标,如果不存在则返回-1
"""
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search_recursive(arr, low, mid - 1, target)
else:
return binary_search_recursive(arr, mid + 1, high, target)
```
在这个算法中,我们首先判断序列的起始下标是否大于终止下标,如果是,则说明找不到目标值,返回-1。否则,我们计算中间下标mid,如果arr[mid]等于目标值,则直接返回mid;否则,我们判断arr[mid]和目标值的大小关系,如果arr[mid]大于目标值,则在左半部分继续查找;否则,在右半部分继续查找。
我们可以将这个算法应用到一个有序列表中,例如:
```python
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search_recursive(arr, 0, len(arr) - 1, target)
print(result)
```
输出:
```
2
```
这表明目标值5在有序列表arr中的下标为2。
阅读全文