大一在读 大数据管理与应用专业 欢迎交流
备战蓝桥杯 倒计时72天
目前主要学习Python算法与数据结构 今日主题：二分查找
在这套流程里 l+1最终等于r 避免以往很多临界左移右移加一减一的讨论情况 并且mid(图片里的m)的范围处在[1,n-1] 真的很棒!
例一：nums为无重复的升序序列
问题分析 ：划分红蓝区域 红区<=target 蓝区>target
若红区最后一个元素等于 target 返回下标 否则返回下标+1
class Solution: def searchInsert(self, nums: List[int], target: int) -> int: l,r=-1,len(nums) while l+1<r: mid=(l+r)//2 if nums[mid]>target: r=mid else: l=mid return l if nums[l]==target else l+1
例二：nums是一个非递减数组（前一篇博客出了下面这道的index解法[不建议使用]没有思考尽管 通过效率很高但还是不建议用这种手段做题）
问题分析：1：找到第一个等于target的数字 划分红蓝区域
红区小于target 蓝区>=target 如果蓝区的第一个元素不等于target(前提是该元素下标可访问) 说明不存在 直接返回[-1,-1]
如果蓝区的第一个元素下标不可访问等价于 l+1>len(nums)-1 返回[-1,-1]
否则返回蓝区的第一个下标X1
2：找到最后一个等于target的数字 划分红蓝区域
红区小于等于target 蓝区大于target
class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: l,r=-1,len(nums) while l+1<r: mid=(l+r)//2 if nums[mid]>=target: r=mid else: l=mid#红区记录<target if l==len(nums)-1:return [-1,-1]#如果不成立 l+1就是其中一个答案 if nums[l+1]!=target:return [-1,-1] l1,r1=l,len(nums) while l1+1<r1: mid=(l1+r1)//2 if nums[mid]>target: r1=mid else: l1=mid#红区记录<=target return [l+1,l1]
我是小郑 期待与你一起奔赴山海！蓝桥杯加油！
