4、编写程序。实现对单调递增的整型序列中(如随机产生10个1-100之间的不重复整数序列), 进行折半查找。用折半查找法找出一个数是数组中第几个元素,如果找到,则返回其下标;如果该数不在数组中,则返回-1 。
时间: 2024-09-14 14:07:31 浏览: 44
randspace:生成单调递增的随机间隔值序列。-matlab开发
折半查找,也称为二分搜索,是一种高效的搜索算法,它适用于有序数组。对于给定的单调递增整型序列,我们可以通过以下步骤实现折半查找:
1. 定义一个函数,比如`binary_search`,接受两个参数:一个有序整数列表`arr`和一个目标值`target`。
2. 初始化两个指针,`low`表示数组的开始下标(0),`high`表示数组的结束下标减一(`len(arr) - 1`)。
3. 当`low`小于等于`high`时,循环执行以下操作:
a. 计算中间索引 `mid`,通常是 `(low + high) // 2`。
b. 检查 `arr[mid]` 是否等于目标值 `target`。
- 如果相等,返回 `mid`,因为找到了目标值的正确位置。
- 如果 `arr[mid]` 大于 `target`,说明目标值应该在左半部分,将`high`设置为 `mid - 1`。
- 否则,如果 `arr[mid]` 小于 `target`,说明目标值应该在右半部分,将`low`设置为 `mid + 1`。
4. 循环结束后如果没有找到目标值,说明目标值不在数组中,返回 `-1`。
下面是这个算法的一个简单Python实现示例:
```python
def binary_search(arr, target):
low = 0
high = 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到100的随机升序数组
import random
random_arr = sorted(random.sample(range(1, 101), 10))
# 使用折半查找函数
index = binary_search(random_arr, 50)
print(f"50在数组中的位置是{index},如果不存在则返回-1")
```
阅读全文