通过递归实现二分查找法,查找列表中(列表中的元素非有序排列)所需要的某个元素,输出要查找的元素xx存在,一共查找了xx次,如未找到,输出要查找的元素xx不存在,一共查找了xx次;
时间: 2023-11-22 07:04:14 浏览: 71
好的,我可以帮你实现这个功能。以下是递归实现二分查找法的代码:
```python
def binary_search(arr, low, high, x, count):
if high >= low:
mid = (high + low) // 2
# 如果找到了要查找的元素,返回True
if arr[mid] == x:
return True, count
# 如果中间元素比要查找的元素大,则在左半部分继续查找
elif arr[mid] > x:
count += 1
return binary_search(arr, low, mid - 1, x, count)
# 否则,在右半部分继续查找
else:
count += 1
return binary_search(arr, mid + 1, high, x, count)
# 如果未找到要查找的元素,返回False
else:
return False, count
```
其中,`arr`是要查找的列表,`low`和`high`是要查找的区间范围,`x`是要查找的元素,`count`是查找的次数。调用这个函数,可以得到要查找的元素是否存在以及查找的次数:
```python
arr = [3, 1, 4, 2, 7, 5]
x = 4
found, count = binary_search(arr, 0, len(arr) - 1, x, 1)
if found:
print("要查找的元素", x, "存在,一共查找了", count, "次")
else:
print("要查找的元素", x, "不存在,一共查找了", count, "次")
```
这里假设要查找的元素为4,列表为[3, 1, 4, 2, 7, 5],输出为:
```
要查找的元素 4 存在,一共查找了 2 次
```
阅读全文