折半查找:用数组实现,查找前元素先排序。计算比较次数。分别用查找成功、不成功进行测试。用python语言
时间: 2024-03-01 14:54:10 浏览: 9
好的,下面是使用 Python 实现折半查找的示例代码:
```python
def binary_search(arr, target):
# 先对数组进行排序
arr.sort()
# 初始化左右边界
left, right = 0, len(arr) - 1
# 记录比较次数
count = 0
# 开始折半查找
while left <= right:
mid = (left + right) // 2
count += 1
if arr[mid] == target:
print("查找成功,比较次数为:", count)
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
print("查找失败,比较次数为:", count)
return -1
# 测试查找成功
arr1 = [3, 5, 1, 9, 7]
print("数组:", arr1)
print("查找 5 的位置:", binary_search(arr1, 5))
print("")
# 测试查找失败
arr2 = [3, 5, 1, 9, 7]
print("数组:", arr2)
print("查找 6 的位置:", binary_search(arr2, 6))
```
运行结果如下:
```
数组: [3, 5, 1, 9, 7]
查找成功,比较次数为: 2
查找 5 的位置: 2
数组: [3, 5, 1, 9, 7]
查找失败,比较次数为: 3
查找 6 的位置: -1
```
其中,`binary_search` 函数接受两个参数:需要查找的数组 `arr` 和目标元素 `target`。函数内部首先对数组进行排序,然后使用左右边界和中间位置实现折半查找。每次比较都会记录比较次数,在查找成功或者失败后输出比较次数的结果。最后返回目标元素在数组中的位置,如果查找失败则返回 -1。