用python编写程序。实现对单调递增的整型序列中(如随机产生10个1-100之间的不重复整数序列),进行折半查找。用折半查找法找出一个数是数组中第几个元素,如果找到,则返回其下标;如果该数不在数组中,则返回-1。
时间: 2024-09-13 09:05:52 浏览: 45
在Python中,你可以通过定义一个二分查找函数来实现这个功能。首先,你需要创建一个列表来存储你的单调递增整数序列,然后实现一个`binary_search`函数来应用折半查找算法。以下是一个简单的实现:
```python
import random
def generate_sorted_array(n, min_val=1, max_val=100):
"""
生成一个指定长度和范围的单调递增整数序列
"""
return sorted(random.sample(range(min_val, max_val + 1), n))
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
# 如果未找到目标值,返回-1
return -1
# 示例
n = 10
arr = generate_sorted_array(n)
target = 50
result = binary_search(arr, target)
if result != -1:
print(f"Number {target} is at index {result}")
else:
print(f"Number {target} not found in the array")
阅读全文