二分查找

步骤

1.寻找二分范围
二分范围可使用开区间(-1,n-1)，对应范围[0,n-2],最后一位不搜索。此时结果返回right。

2.确定染色规则(可能要讨论)

3.染色
第二步为Ture,right左移，右侧染蓝;  否则left右移，左侧染红。

例题

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        #[0,n-1]
        #(-1,n-1)
        left=-1
        right=len(nums)-1
        while left+1<right:
            mid=(left+right)//2
            if nums[mid]>nums[mid+1]:
                right=mid
            else:
                left=mid
        return right

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left=-1
        right=len(nums)-1
        while left+1<right:
            mid = (left+right)//2
            if nums[mid]<nums[-1]:
                right=mid
            else:
                left=mid
        return nums[right]

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def is_blue(i:int)->bool:
            end=nums[-1]
            if nums[i]>end:
                return target>end and nums[i]>=target
            else:
                return target>end or nums[i]>=target
        # 开区间（-1，n-1） 对应二分范围 [0,n-2]
        left=-1
        right=len(nums)-1
        while left+1<right:
            mid=(left+right)//2
            if is_blue(mid):
                right=mid
            else:
                left=mid
        return -1 if right>len(nums)-1 or nums[right]!=target else right