用python写出一个:输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x,使用二分查找算法查找x,输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。 输入格式: 输入共三行: 第一行是n值; 第二行是n个整数; 第三行是x值。 输出格式: 输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。
时间: 2024-02-06 17:12:31 浏览: 73
好的,下面是使用二分查找算法查找x的 Python 代码:
```python
n = int(input()) # 输入n值
nums = list(map(int, input().split())) # 输入n个非降序排列的整数
x = int(input()) # 输入要查找的数x
left = 0
right = n - 1
count = 0 # 记录比较次数
while left <= right:
mid = (left + right) // 2
count += 1
if nums[mid] == x:
print(mid, count)
break
elif nums[mid] < x:
left = mid + 1
else:
right = mid - 1
else:
print(-1, count) # 没有找到x,输出-1和比较次数
```
程序首先读入 n、n个非降序排列的整数以及要查找的数 x。然后定义 left、right 指针分别指向数组的左右端点,count 变量用于记录比较次数。
程序在 while 循环中进行二分查找:先计算中间位置 mid,然后比较 nums[mid] 和 x 的大小,如果 nums[mid] 等于 x,则找到了 x,输出 mid 和 count 并结束程序;如果 nums[mid] 小于 x,则将 left 指针右移;如果 nums[mid] 大于 x,则将 right 指针左移。
如果循环结束仍然没有找到 x,则说明 x 不存在于数组中,输出 -1 和 count。
阅读全文