编程题:输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x,使用二分查找算法查找x,输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。 输入格式: 输入共三行: 第一行是n值; 第二行是n个整数; 第三行是x值。 输出格式: 输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。
时间: 2024-03-22 22:40:02 浏览: 114
以下是一个 Python 的示例代码:
```python
n = int(input())
nums = list(map(int, input().split()))
x = int(input())
left, right = 0, 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)
```
代码逻辑比较简单,首先读入 n 和 n 个整数,以及要查找的 x 值。然后使用 left 和 right 分别表示查找区间的左右边界,初始化为数组的第一个和最后一个元素的下标。同时使用 count 记录比较次数,初始化为 0。
在 while 循环中,每次将查找区间缩小一半,如果中间元素等于 x,就找到了,输出下标和比较次数。如果中间元素小于 x,就在右半边查找;如果中间元素大于 x,就在左半边查找。最后如果循环结束仍然没有找到 x,就输出 -1 和比较次数。
值得注意的是,在 while 循环的末尾有一个 else 分支,如果 while 循环是正常结束的(即没有被 break 中断),就会执行这个 else 分支,输出 -1 和比较次数。
阅读全文