4.二分查找法查找列表中(列表中的元素非有序排列)所需要的某个元素(通过中位法获取对应的元素值,进行叠代查找比较,直至找到所需要的元素),输出要查找的元素xx存在,在下标为xx处,一共查找了xx次,如未找到,输出要查找的元素xx不存在,一共查找了xx次;(要查找的元素即为自己学号后两位,要求要有找到及未找到两种测试用例);
时间: 2023-11-13 14:04:14 浏览: 65
以下是 Python 实现的代码:
```python
def binary_search(arr, target):
"""
二分查找法查找列表中的某个元素
:param arr: 待查找的列表
:param target: 要查找的元素
:return: 如果找到了要查找的元素,返回元素所在的下标;否则返回 -1
"""
low = 0
high = len(arr) - 1
count = 0
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
count += 1
if guess == target:
return mid, count
if guess > target:
high = mid - 1
else:
low = mid + 1
return -1, count
# 测试用例
arr = [15, 9, 32, 8, 12, 7, 11, 20, 23, 6]
target1 = 63 # 不存在
target2 = 20 # 存在
result1, count1 = binary_search(arr, target1)
result2, count2 = binary_search(arr, target2)
# 输出结果
if result1 == -1:
print("要查找的元素{}不存在,一共查找了{}次".format(target1, count1))
else:
print("要查找的元素{}存在,在下标为{}处,一共查找了{}次".format(target1, result1, count1))
if result2 == -1:
print("要查找的元素{}不存在,一共查找了{}次".format(target2, count2))
else:
print("要查找的元素{}存在,在下标为{}处,一共查找了{}次".format(target2, result2, count2))
```
输出结果:
```
要查找的元素63不存在,一共查找了4次
要查找的元素20存在,在下标为7处,一共查找了3次
```
其中,`binary_search` 函数接受一个列表 `arr` 和要查找的元素 `target`,返回一个元组 `(index, count)`,其中 `index` 为要查找的元素在列表中的下标(如果找到),`count` 为查找次数。
测试用例分别为要查找的元素不存在和存在两种情况,输出查找结果及查找次数。
阅读全文