编写程序。实现对单调递增的整型序列中(如随机产生10个1-100之间的不重复整数序列),进行折半查找。用折半查找法找出一个数是数组中第几个元素,如果找到,则返回其下标;如果该数不在数组中,则返网-1。
时间: 2024-09-13 11:17:11 浏览: 67
二分实现两个递增序列中位数查找
编写程序来实现折半查找算法,首先需要创建一个随机生成的、单调递增的整数序列。这里是一个简单的Python示例:
```python
import random
def generate_sorted_sequence(n, min_val=1, max_val=100):
"""
生成一个包含n个随机整数的有序序列。
"""
return sorted(random.sample(range(min_val, max_val + 1), n))
def binary_search(sequence, target):
"""
使用折半查找法寻找目标值在有序序列中的位置。
如果找到,返回下标;否则返回-1。
"""
left, right = 0, len(sequence) - 1
while left <= right:
mid = (left + right) // 2
if sequence[mid] == target:
return mid
elif sequence[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 生成一个包含10个随机数的有序序列
sequence = generate_sorted_sequence(10)
# 示例查找操作
target = random.choice(sequence)
index = binary_search(sequence, target)
print(f"Target {target} is at index {index}. If not found, returns -1.")
```
在这个程序中,我们首先生成了一个1到100之间的随机整数序列,并确保它们是不重复的。然后,我们定义了一个`binary_search`函数,它接收这个有序序列和一个目标值,通过不断将搜索范围减半来查找目标值的位置。如果找到,返回对应下标;未找到则返回-1。
阅读全文