用Python写出二分查找法查找列表中(列表中的元素非有序排列)所需要的某个元素(通过中位法获取对应的元素值,进行叠代查找比较,直至找到所需要的元素),输出要查找的元素xx存在,在下标为xx处,一共查找了xx次,如未找到,输出要查找的元素xx不存在,一共查找了xx次(要用回归函数)
时间: 2023-06-20 09:09:05 浏览: 32
这是一个简单的二分查找实现:
```python
def binary_search(arr, x):
low = 0
high = len(arr) - 1
count = 0
while low <= high:
mid = (low + high) // 2
count += 1
if arr[mid] == x:
return mid, count
elif arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1, count
# 测试代码
arr = [3, 7, 5, 8, 4, 2, 9, 1, 6]
x = 5
idx, count = binary_search(arr, x)
if idx != -1:
print(f"要查找的元素{x}存在,在下标为{idx}处,一共查找了{count}次")
else:
print(f"要查找的元素{x}不存在,一共查找了{count}次")
```
这个实现的时间复杂度为$O(\log n)$,其中$n$为列表中元素的数量。