使用递归函数实现下列数列的二分查找(代码和运行结果截图) 查找下列列表中是否有0-7数字,有则返回数字所在位置,无则返回-1。 a[7]={1,4,5,7,10,16,19}
时间: 2024-10-14 20:02:10 浏览: 46
为了实现二分查找算法用于给定的列表 `a[7] = {1, 4, 5, 7, 10, 16, 19}` 中寻找指定数字是否在其中,我们首先需要定义一个递归函数。在这个例子中,假设列表已经排序,因为我们通常会在二分查找中假设输入数据有序。
递归函数的基本思路是:如果列表为空,则返回 -1;如果中间元素等于目标值,返回中间索引;如果中间元素大于目标值,对左半部分递归查找;如果小于目标值,对右半部分递归查找。
下面是使用Python实现的代码:
```python
def binary_search(arr, target, low=0, high=None):
# 如果high未提供,默认为数组长度减一
if high is None:
high = len(arr) - 1
# 基本情况:low > high 或者 target 等于中间元素
if low > high or (low == high and arr[low] != target):
return -1
mid = (low + high) // 2 # 计算中间索引
# 如果中间元素等于目标值,返回索引
if arr[mid] == target:
return mid
# 否则,如果目标值小于中间元素,搜索左半部分
elif arr[mid] > target:
return binary_search(arr, target, low, mid - 1)
# 否则,搜索右半部分
else:
return binary_search(arr, target, mid + 1, high)
# 测试列表 a[7]
arr = [1, 4, 5, 7, 10, 16, 19]
target = 0 # 检查是否存在0
result = binary_search(arr, target)
print(f"查找 {target} 的结果: {result}")
```
请注意,这个代码片段并没有包含实际的运行结果截图,因为在这里我无法直接展示。你可以复制这段代码到Python环境中运行,查看输出的结果。
阅读全文