Python用递归实现 二分查找法查找列表中(列表中的元素非有序排列)所需要的某个元素(通过中位法获取对应的元素值,进行叠代查找比较,直至找到所需要的元素),输出要查找的元素xx存在,在下标为xx处,一共查找了xx次,如未找到,输出要查找的元素xx不存在,一共查找了xx次;
时间: 2023-12-04 09:03:17 浏览: 80
包含了剑指offer第二版上收录的近70道编程题,由python实现.zip
好的,我可以为您提供一个递归实现的二分查找算法的代码示例:
```python
def binary_search(arr, target, low, high, count):
"""
二分查找算法的递归实现
:param arr: 目标列表
:param target: 目标元素
:param low: 查找范围的下界
:param high: 查找范围的上界
:param count: 查找次数
:return: 目标元素在列表中的索引位置,如果不存在则返回 -1
"""
if low > high:
# 如果查找范围为空,则说明未找到目标元素
print(f"要查找的元素{target}不存在,一共查找了{count}次")
return -1
mid = (low + high) // 2
if arr[mid] == target:
# 如果找到了目标元素,则返回其在列表中的索引位置
print(f"要查找的元素{target}存在,在下标为{mid}处,一共查找了{count}次")
return mid
elif arr[mid] > target:
# 如果中间元素大于目标元素,则在左半部分继续查找
return binary_search(arr, target, low, mid-1, count+1)
else:
# 如果中间元素小于目标元素,则在右半部分继续查找
return binary_search(arr, target, mid+1, high, count+1)
```
您可以将要查找的列表、目标元素、查找范围的下界和上界作为参数传入该函数中。初始时,下界为0,上界为列表长度减1。调用该函数时,将查找次数初始化为0,然后依次查找下标为low到high的元素。如果找到目标元素,则直接返回其在列表中的索引位置;如果查找范围为空,则说明未找到目标元素,返回-1。
阅读全文