【基础算法精讲-学习记录】二分查找2

视频学习记录

https://www.bilibili.com/video/BV1QK411d76w

• 这节课讲得是二分查找的灵活运用，比如找数组中的小峰值和那种旋转排序数组的最小值都可以用。核心是通过二分判断一半的数据性质。

例题和课后作业代码记录

162. 寻找峰值

https://leetcode.cn/problems/find-peak-element/description/

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        # 由于相邻元素值不同，可以通过二分查找，直接切入到某个峰值的左右侧然后迅速逼近
        # 在这里定，红色就是指针往左，蓝色是峰值以及峰值往右，由于最右边的值必定蓝色，所以不在二分区间
        # 时间 Ologn，空间 O1
        n = len(nums)
        left = 0
        right = n - 2
        while left <= right:
            mid = (left+right)//2 
            if nums[mid] >= nums[mid+1]:
                right = mid - 1
            else:
                left = mid + 1
        # print(left, right)
        return left

153. 寻找旋转排序数组中的最小值

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/

class Solution:
    def findMin(self, nums: List[int]) -> int:
        # 由于旋转后，就会变成数组中存在一个峰值，如果规定红色为峰值左侧，蓝色为峰值或峰值右侧
        # 那么数组最右侧必定为蓝色，所以要染色的区域是0-n-2（n为长度）
        # 唯一的基准就是最右侧，如果取到的中间值比最右侧小，说明从这个中间值到最右侧都是最小值右边
        # 时间 Ologn，空间 O1
        n = len(nums) 
        left = 0
        right = n-2
        while left <= right:
            mid = (left+right)//2 
            if nums[mid] > nums[-1]:
                left = mid + 1
            else:
                right = mid - 1
        return nums[left]

33. 搜索旋转排序数组

https://leetcode.cn/problems/search-in-rotated-sorted-array/description/

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 可以先把最小值找到，然后先看target是否在最小值到最右边之间，不在的话考虑最小值左边，各用二分
        # 找到最小值和第二次二分都是Ologn，所以时间Ologn，空间O1
        n = len(nums) 
        left = 0
        right = n-2
        while left <= right:
            mid = (left+right)//2 
            x = nums[mid]
            if target > nums[-1] >= x:
                # 说明target在第一段，x在第二段
                right = mid - 1
            elif x > nums[-1] >= target:
                # 说明target在第二段，x在第一段
                left = mid+1
            # 下面两种情况都是同一段，按普通二分处理
            elif x >= target:
                right = mid - 1
            else:
                left = mid + 1
        return left if nums[left] == target else -1

        # 除了下面这种两次二分的办法，也可以判断target、中间值和最后一个值的关系来锁定中间值和target关系
        n = len(nums) 
        left = 0
        right = n-2
        while left <= right:
            mid = (left+right)//2 
            if nums[mid] > nums[-1]:
                left = mid + 1
            else:
                right = mid - 1
        min_index = left 

        # 先排除超出范围的
        if nums[min_index] > target or ((min_index > 0 and target > nums[min_index-1]) or (min_index == 0 and target > nums[-1])):
            return -1 
        
        if nums[min_index] <= target <= nums[-1]:
            target_index = bisect_left(nums, target, min_index)
            if nums[target_index] == target:
                return target_index
            else:
                return -1 
        else:
            target_index = bisect_left(nums, target, 0, min_index)
            if nums[target_index] == target:
                return target_index
            else:
                return -1 

74. 搜索二维矩阵

https://leetcode.cn/problems/search-a-2d-matrix/description/

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 时间2logn，空间 1
        # 行内非严格递增，并且每行第一个数字大于前一行最后一个，也就是可以先判断在哪个行再找
        last_num = [m[-1] for m in matrix]
        # 排除数字不在其中的情况
        if target < matrix[0][0] or target > last_num[-1]:
            return False
        
        # 由于已经确定数字必定在这个区间，所以col index不会大于等于第一维长度
        col_index = bisect_left(last_num, target)
        idx = bisect_left(matrix[col_index], target)
        if matrix[col_index][idx] == target:
            return True 
        else:
            return False

1901. 寻找峰值 II

https://leetcode.cn/problems/find-a-peak-element-ii/description/

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        # 这题0x3f的解法很有意思，二分是找行，然后取其中最大的值与另一行的相同位置比较
        # 如果比另一行更小，说明另一端必有峰值。最后指针所指行中的最大值就是峰值
        # 最大值保证了左右就是最大，上下的最大只要不断二分就能得出
        left, right = 0, len(mat)-2
        while left <= right:
            mid = (left+right)//2
            mx = max(mat[mid])
            if mx > mat[mid+1][mat[mid].index(mx)]:
                right = mid - 1
            else:
                left = mid + 1
        return [left, mat[left].index(max(mat[left]))]

154. 寻找旋转排序数组中的最小值 II

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/

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