Python全系列 教程
3567个小节阅读:5929.8k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本,未来主流的版本
人工智能 教程
顺势而为,AI创新未来
大厂算法 教程
算法,程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
整体流程保持不变,每轮先计算中点索引 mid ,再判断 target
和 nums[mid]
的大小关系,分为以下几种情况。
当 nums[m] < target
或 nums[m] > target
时,说明还没有找到 target
,因此采用普通二分查找的缩小区间操作,从而使指针 left 和 right 向 target
靠近
当 nums[m] == target
时,说明小于 target
的元素在区间 [left,mid−1] 中,因此采用 right=mid−1 来缩小区间,从而使指针 right 向小于 target
的元素靠近
循环完成后,left 指向最左边的 target
,right 指向首个小于 target
的元素,因此索引 left 就是插入点
xxxxxxxxxx
def search_binary_insert(nums:list[int],target) -> int:
'''二分查找插入点-有重复数据的情况'''
left = 0
right = 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:
# 和原来不一样的时候
right = mid -1
return left
if __name__ == '__main__':
data = [1,2,3,6,6,6,7,8,9]
index = search_binary_insert(data,7)
print(index)