随机输入一组有序元素。然后随机输入一个数,用折半查找法在数组中查找,如在数组中,则输出元素在数组中的位置;如不在,则输出提示。
时间: 2024-11-27 11:18:20 浏览: 6
java 折半查找法(二分查找)实例
5星 · 资源好评率100%
折半查找,也称为二分查找,是一种在有序数组中查找特定元素的高效算法。它的基本思想是每次将搜索区间缩小一半,直到找到目标元素或者确定目标元素不存在。
以下是使用Python实现折半查找的基本步骤:
1. 确保输入的是一组已排序的数组。假设我们有一个名为`arr`的列表,它存储了我们的有序元素。
2. 定义一个函数`binary_search`,接受两个参数:待查数组`arr`和目标值`target`。
3. 初始化两个变量,`low`表示搜索区间的起始下标,`high`表示搜索区间的结束上标,它们最初都是数组的第一个元素和最后一个元素的索引。
4. 当`low`小于等于`high`时,执行循环:
a. 计算中间索引 `mid`,通常是 `(low + high) // 2`。
b. 比较目标值 `target` 和中间元素 `arr[mid>`:
- 如果相等,返回`mid`,因为找到了目标元素的位置。
- 如果目标值小于中间元素,说明目标应在左半部分,更新`high`为`mid - 1`。
- 如果目标值大于中间元素,说明目标应在右半部分,更新`low`为`mid + 1`。
5. 如果搜索结束后没有找到目标元素,返回-1或其他适当的提示,表示元素不在数组中。
这是一个简单的示例代码:
```python
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # 如果没有找到,返回-1
# 使用示例
arr = [1, 2, 3, 4, 5]
target = int(input("请输入一个数字: "))
result = binary_search(arr, target)
if result != -1:
print(f"元素 {target} 的位置是 {result}")
else:
print(f"{target} 不在数组中")
```
阅读全文