请编写一个程序,能够通过基于递归实现的二分查找法从其中快速找到指定的数值,并返回对应数值的索引。注意:待查找序列中的数值为升序排列。
时间: 2024-10-29 20:13:23 浏览: 8
python二分查找算法的递归实现方法
5星 · 资源好评率100%
当然,这是一个简单的Python示例,演示了如何使用递归实现二分查找算法:
```python
def binary_search(arr, low, high, target):
if high >= low:
mid = (high + low) // 2
# 如果中间元素正好是我们正在寻找的目标
if arr[mid] == target:
return mid
# 如果目标小于中间元素,则在左半部分继续搜索
elif arr[mid] > target:
return binary_search(arr, low, mid - 1, target)
# 如果目标大于中间元素,则在右半部分继续搜索
else:
return binary_search(arr, mid + 1, high, target)
# 如果序列为空或者目标不在序列中,返回 None
else:
return -1
# 使用方法
arr = [1, 3, 5, 7, 9, 11, 13]
target = 9
result_index = binary_search(arr, 0, len(arr) - 1, target)
if result_index != -1:
print("找到目标值 {} 的索引是 {}".format(target, result_index))
else:
print("目标值 {} 没有在数组中找到".format(target))
```
这个函数会接受一个升序排列的列表 `arr` 和两个边界 `low` 和 `high` 作为输入,然后递归地将搜索范围缩小到一半,直到找到目标值或者确定其不存在为止。
阅读全文