Leedcode 二分查找每日两练 Python

大一在读 大数据管理与应用专业 欢迎交流

备战蓝桥杯 倒计时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]

我是小郑 期待与你一起奔赴山海！蓝桥杯加油！