python中请实现有重复数字的有序数组的二分查找。 输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。 输入格式: 输入第一行有两个数,第一个数为数组长度n(≤10^6),第二个数为需要查找的数。 接下来有n个整数,以空格或换行符分隔。 输出格式: 输出待查找的数的位置。
时间: 2024-03-01 17:55:45 浏览: 33
以下是实现该功能的Python代码:
```python
n, target = map(int, input().split())
nums = list(map(int, input().split()))
left, right = 0, n - 1
ans = n + 1
while left <= right:
mid = (left + right) // 2
if nums[mid] >= target:
ans = mid
right = mid - 1
else:
left = mid + 1
print(ans + 1)
```
解释:
首先读入数组长度和查找值,以及数组本身。
接着,定义左右指针分别指向数组的第一个和最后一个位置,以及一个变量 `ans` 来记录第一个大于等于查找值的位置(初始值设置为数组长度加一,以便处理数组中不存在这样的数的情况)。
然后,进入循环,当左指针小于等于右指针时,执行二分查找。将中间位置 `mid` 计算为左右指针的平均值,如果该位置的数大于等于查找值,则将 `ans` 更新为该位置,并将右指针移到 `mid` 的左边继续查找;否则将左指针移到 `mid` 的右边继续查找。
最后,输出 `ans+1` 即为待查找的数的位置。
相关问题
python请实现有重复数字的有序数组的二分查找。输出在数组中第一个大于等于查找值的位置
好的,下面是 python 代码实现:
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] >= target:
if mid == 0 or arr[mid-1] < target:
return mid
else:
right = mid - 1
else:
left = mid + 1
return -1
```
这个函数接收两个参数:一个有重复数字的有序数组 `arr` 和一个查找值 `target`。函数返回的是在数组中第一个大于等于查找值的位置,如果不存在,则返回 -1。
算法的思想是标准的二分查找,只是当找到目标值时需要进行一些特殊处理,即继续向左查找直到找到第一个大于等于目标值的位置。
注意:这个算法的时间复杂度是 O(log n),因为它是基于二分查找的。
本关任务:采用二分查找算法实现查找有序数组里大于等于 x 的第一个数字
以下是使用二分查找算法实现查找有序数组里大于等于 x 的第一个数字的Python代码:
```python
def binary_search(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] >= x:
if mid == 0 or arr[mid - 1] < x:
return mid
else:
right = mid - 1
else:
left = mid + 1
return -1
```
其中,arr为有序数组,x为要查找的数字。函数返回大于等于x的第一个数字的下标,如果不存在则返回-1。
举个例子,假设有序数组为[1, 3, 5, 7, 9],要查找大于等于6的第一个数字,那么调用函数binary_search(arr, 6)后会返回2,即数字5的下标。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)