请用python实现请实现有重复数字的有序数组的二分查找。 输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。 输入格式: 输入第一行有两个数,第一个数为数组长度n(≤10^6),第二个数为需要查找的数。 接下来有n个整数,以空格或换行符分隔。 输出格式: 输出待查找的数的位置。
时间: 2024-03-17 10:40:10 浏览: 62
python 实现 数组中重复的数字
好的,这是一个比较典型的二分查找问题,以下是实现的代码:
```python
n, target = map(int, input().split())
nums = list(map(int, input().split()))
left, right = 0, n - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
if left < n and nums[left] >= target:
print(left)
else:
print(n + 1)
```
首先,我们把输入的数组按从小到大的顺序排好。然后我们定义两个指针 left 和 right 分别指向数组的最左和最右的位置。接下来,我们每次取中间位置的数 mid,并与要查找的数 target 对比。如果 mid 大于等于 target,则说明 target 可能存在于 mid 的左边或者 mid 位置上,我们就把 right 指针指向 mid 左边一个位置,继续查找。否则,说明 target 可能存在于 mid 的右边,我们就把 left 指针指向 mid 右边一个位置,继续查找。
最后,我们判断 left 是否小于 n 并且 nums[left] 是否大于等于 target,如果是,则说明找到了第一个大于等于 target 的位置,直接输出 left;否则,说明数组中不存在这样的数,输出 n+1。
阅读全文