请用python代码回答:二分查找法查找序列类型中所需要的元素,使用递归方式实现,直至找到所需要的元素,输出要查找的元素xx存在,在下标为xx处,一共查找了xx次,如未找到,输出要查找的元素xx不存在,一共查找了xx次;
时间: 2023-11-14 07:05:00 浏览: 67
好的,以下是一个使用递归实现二分查找,并输出查找结果及查找次数的Python代码:
```python
def binary_search_recursive(arr, target, low, high, count):
"""
使用递归实现二分查找
:param arr: 有序列表
:param target: 要查找的目标
:param low: 当前查找范围的左侧索引
:param high: 当前查找范围的右侧索引
:param count: 查找次数
:return: 目标在列表中的索引,没找到返回-1
"""
if low > high:
return -1, count
mid = (low + high) // 2
if arr[mid] == target:
return mid, count
elif arr[mid] > target:
return binary_search_recursive(arr, target, low, mid - 1, count + 1)
else:
return binary_search_recursive(arr, target, mid + 1, high, count + 1)
if __name__ == '__main__':
# 示例列表
lst = [1, 3, 4, 6, 8, 10, 11, 12, 14, 15, 18, 19, 20]
# 要查找的元素
target = int(input("请输入要查找的元素:"))
# 查找目标在列表中的索引和查找次数
index, count = binary_search_recursive(lst, target, 0, len(lst) - 1, 1)
# 判断查找结果并输出
if index == -1:
print(f"要查找的元素{target}不存在,一共查找了{count}次")
else:
print(f"要查找的元素{target}存在,在下标为{index}处,一共查找了{count}次")
```
这个程序和上一个问题的程序类似,只不过在`binary_search_recursive`函数中增加了一个表示查找次数的参数`count`。每次递归时,将`count`加1,最终返回查找次数和查找结果。在主函数中,根据查找结果输出相应的信息,并将查找次数输出。
阅读全文