第零章：我写了首诗，让你闭着眼睛也能写对二分搜索

labuladong 我写了首诗，让你闭着眼睛也能写对二分搜索

• 二分查找的一个技巧是：不要出现 else，而是把所有情况用 elif 列出来，这样可以清楚地展现所有细节
• mid=left + (right - left) // 2 可防止溢出
• 对于左右侧边界的二分查找，elif nums[mid]==target 时更新的边界不一样。while循环结束后要通过打补丁的方式返回结果

  基本二分查找

class Solution(object):
    def search(self, nums, target):
        left=0
        right=len(nums)-1
        while left<=right:
            mid=left+(right-left)//2
            if nums[mid]<target:
                left=mid+1
            elif nums[mid]>target:
                right=mid-1
            elif nums[mid]==target:
                return mid
        return -1

寻找左右侧边界的二分查找

class Solution(object):
    def searchRange(self, nums, target):

        def leftSearch(nums,target):
            left=0
            right=len(nums)-1
            while left<=right:
                mid=left+(right-left)//2
                if nums[mid]<target:
                    left=mid+1
                elif nums[mid]>target:
                    right=mid-1
                elif nums[mid]==target:
                    right=mid-1
            # 注意此处的打补丁，因为是左边界，所以是 nums[left]!=target
            if left>=len(nums) or nums[left]!=target:
                return -1
            return left
            # # 或者
            # if left<=len(nums)-1 and nums[left]==target: # 因为while中使用<=,所以要确保left没有越界
            #     return left
            # return -1

        def rightSearch(nums,target):
            left=0
            right=len(nums)-1
            while left<=right:
                mid=left+(right-left)//2
                if nums[mid]<target:
                    left=mid+1
                elif nums[mid]>target:
                    right=mid-1
                elif nums[mid]==target:
                    left=mid+1
            # 注意此处的打补丁，因为是右边界，所以是 nums[right]!=target
            if right<0  or nums[right]!=target:
                return -1
            return right
            # 或者
            # if right>=0 and nums[right]==target:
            #     return right
            # return -1

        l=leftSearch(nums,target)
        r=rightSearch(nums,target)
        return [l,r]