R7-二分查找篇

目录

双指针

二分优化 

ps:

思路：

双指针

直接用双指针回缩啊

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:ret=[-1,-1]left,right=0,len(nums)-1while left<len(nums):if nums[left]==target:ret[0]=leftbreakleft+=1while right>=0:if nums[right]==target:ret[1]=rightbreakright-=1return ret

 

二分优化 

复杂度比较高，可以考虑使用二分查找优化。

突然有点印象，之前用的是二分查找，一个很好的思路：

bi_find二分查找函数返回left值，那第一次出现的位置start=left

然后比较start和len(nums)的关系（相等--》（-1，-1））

或者找不到？

接着是找到的情况，这是我们只需再调用该函数查找target+1的初始位置-1即可。

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def bi_find(nums,target):left,right=0,len(nums)-1while left<=right:mid=(left+right)//2if nums[mid]<target:left=mid+1else:right=mid-1return leftstart=bi_find(nums,target)if start==len(nums) or nums[start]!=target:return [-1,-1]end=bi_find(nums,target+1)-1return [start,end] 

 

ps:

这里时间复杂度感觉受到target+1的值是否存在影响，例如2直接到1000，中间还会二分查找998遍，所以会复杂。