输入n(n<100)的值,以及n个从小到大排序的整数序列,再输入一个待查找的整数m,使用二分法进行查找该数的序号输入:第一行为整数 n,第二行包括 n个整数,以空格分隔,第三行为整数 m。 输出:如果能够在序列中找到整数 m,则输出其编号(编号从1开始,如果存在多个编号,则返回编号最小的),否则输出 None。。
时间: 2023-07-15 13:14:02 浏览: 119
python练习题 :用户任意输入10个整数到列表中,然后由大到小排列并输出。
以下是Python实现代码:
```python
n = int(input())
nums = list(map(int, input().split()))
m = int(input())
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == m:
while mid > 0 and nums[mid - 1] == m:
mid -= 1
print(mid + 1)
break
elif nums[mid] < m:
left = mid + 1
else:
right = mid - 1
else:
print("None")
```
首先读入整数n、排序后的整数序列nums和待查找的整数m。
然后初始化二分查找的初始区间[left, right]为整个序列。在每一轮循环中,计算区间的中点mid,并比较nums[mid]与m的大小关系。
如果nums[mid]等于m,则找到了待查找的整数,需要在序列中找到编号最小的位置。这里通过向左移动mid来找到第一个等于m的位置,并输出其编号(注意编号从1开始)。
如果nums[mid]小于m,则需要在[mid+1, right]范围内查找m。
如果nums[mid]大于m,则需要在[left, mid-1]范围内查找m。
如果整个循环结束仍然没有找到m,则输出None。
阅读全文