如果待查找列表为升序列表且有重复元素,比如有两个6, 我想用二分查找算法应该如何得到第二个6的下标,用python求解
时间: 2024-04-30 10:22:43 浏览: 18
可以使用二分查找的变形——查找最后一个等于给定值的元素的方法来得到第二个6的下标。具体做法是:
1. 初始化左右指针left和right分别指向列表的起始和末尾位置。
2. 当left <= right时,执行以下步骤:
1)计算中间位置mid = (left + right) // 2。
2)如果mid对应的元素小于目标值,说明目标值在[mid+1, right]区间内,更新left为mid+1。
3)如果mid对应的元素大于目标值,说明目标值在[left, mid-1]区间内,更新right为mid-1。
4)如果mid对应的元素等于目标值,说明找到了一个匹配,但不确定它是不是最后一个匹配,因此更新left为mid+1,继续在[mid+1, right]区间内查找,直到left > right。
3. 最终,left所对应的位置就是最后一个等于目标值的位置,即第二个6的下标。
下面是Python代码实现:
```python
def binary_search_last(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return right # 或者返回left-1,结果是一样的
```
假设列表为[1, 2, 3, 4, 6, 6, 7, 8, 9],要查找第二个6的下标,可以调用上面的函数:
```python
nums = [1, 2, 3, 4, 6, 6, 7, 8, 9]
target = 6
idx = binary_search_last(nums, target)
print(idx) # 输出5
```
可以看到,函数返回的下标为5,即第二个6的位置。
相关推荐
![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_column_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)
![](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)