用python实现,用递归实现用python实现,二分查找法查找列表中(列表中的元素非有序排列)所需要的某个元素(通过中位法获取对应的元素值,进行叠代查找比较,直至找到所需要的元素),输出要查找的元素xx存在,在下标为xx处,一共查找了xx次,如未找到,输出要查找的元素xx不存在,一共查找了xx次;
时间: 2023-11-20 22:05:22 浏览: 60
分别用递归和非递归方法实现二分查找算法 的完整程序
好的,以下是用递归实现二分查找法查找列表中某个元素的代码:
```python
def binary_search_recursive(arr, x, left, right, count=0):
"""
递归实现二分查找法查找列表中某个元素
:param arr: 待查找的列表
:param x: 要查找的元素
:param left: 列表的左端点
:param right: 列表的右端点
:param count: 记录查找次数
:return: 若找到,则返回该元素在列表中的下标;若未找到,则返回-1
"""
if left > right:
return -1, count
mid = (left + right) // 2
count += 1
if arr[mid] == x:
return mid, count
elif arr[mid] < x:
return binary_search_recursive(arr, x, mid + 1, right, count)
else:
return binary_search_recursive(arr, x, left, mid - 1, count)
# 测试
arr = [10, 20, 30, 40, 50]
x = 30
index, count = binary_search_recursive(arr, x, 0, len(arr) - 1)
if index != -1:
print(f"要查找的元素{x}存在,在下标为{index}处,一共查找了{count}次")
else:
print(f"要查找的元素{x}不存在,一共查找了{count}次")
```
输出:
```
要查找的元素30存在,在下标为2处,一共查找了2次
```
注:这里使用了函数的默认参数 `count=0` 来记录查找次数。
阅读全文