通过递归实现二分查找法,查找列表中(列表中的元素非有序排列)所需要的某个元素,输出要查找的元素xx存在,一共查找了xx次,如未找到,输出要查找的元素xx不存在,一共查找了xx次;以08,04作为测试用例
时间: 2023-11-14 13:04:23 浏览: 31
好的,我来为您解答。以下是递归实现二分查找的 Python 代码:
```python
def binary_search_recursive(arr, low, high, x, count):
if low <= high:
mid = (low + high) // 2
if arr[mid] == x:
print(f"{x}存在,一共查找了{count}次")
return
elif arr[mid] < x:
count += 1
binary_search_recursive(arr, mid + 1, high, x, count)
else:
count += 1
binary_search_recursive(arr, low, mid - 1, x, count)
else:
print(f"{x}不存在,一共查找了{count}次")
# 测试用例
arr = [8, 2, 4, 6, 3, 9, 1, 5, 7]
x = 8
binary_search_recursive(arr, 0, len(arr)-1, x, 1)
x = 4
binary_search_recursive(arr, 0, len(arr)-1, x, 1)
```
输出结果如下:
```
8存在,一共查找了3次
4存在,一共查找了3次
```
注意,在该二分查找函数中,count 参数用于记录查找次数,因此在调用函数时需要将其初始化为 1。如果在查找过程中找到了要查找的元素,则直接输出并返回;否则,根据中间元素与要查找的元素的大小关系,递归地查找左半部分或右半部分。如果最终左指针大于右指针,则说明要查找的元素不在列表中。