【2025-02-26】基础算法：二分查找（二）

📝前言说明：
●本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，主要跟随B站博主灵茶山的视频进行学习，专栏中的每一篇文章对应B站博主灵茶山的一个视频
●题目主要为B站视频内涉及的题目以及B站视频中提到的“课后作业”。
●文章中的理解仅为个人理解。
●文章中的截图来源于B站博主灵茶山，如有侵权请告知。

🎬个人简介：努力学习ing
📋本专栏：python刷题专栏
📋其他专栏：C语言入门基础以及python入门基础
🎀CSDN主页愚润求学

二分查找

一，视频题目
- 1，162. 寻找峰值
- 2，153. 寻找旋转排序数组中的最小值
- 3，33. 搜索旋转排序数组
二，课后作业
- 1，1901. 寻找峰值
- 2，154. 寻找旋转排序数组中的最小值

一，视频题目

1，162. 寻找峰值

●题目：
在这里插入图片描述

●题解：

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 2
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > nums[mid + 1]: # 说明[0,mid] 必有一个峰值
                right = mid - 1 # 判断清楚收缩方向
            else: 
                left = mid + 1
        return right + 1

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

在这里插入图片描述

class Solution:
    def findMin(self, nums: List[int]) -> int:
        # 以数组最后一个数为基准，配合mid来判断最小值的位置
        # 1，如果nums[mid] > nums[-1]: 则最小值一定在mid的右侧（可证），向右收缩
        # 2，如果nums[mid] < nums[-1]: 则最小值一定在mid的左侧，向左收缩
        left, right = 0, len(nums) - 2
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > nums[-1]:
                left = mid + 1
            else:
                right = mid - 1
        return nums[left] # left 指向的是满足（nums[mid] > nums[-1]）的右边一个，又因为最小值在右侧，所以left指向的就是最小值

3，33. 搜索旋转排序数组

在这里插入图片描述

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def check(mid:int) -> bool:
            x = nums[mid]
            if x > nums[-1]: # 借助数组最后一个数字间接判断: x是否在target右边
                return target > nums[-1] and x >= target
            else:
                return target > nums[-1] or x >= target
        left, right =0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left if nums[left] == target else -1

二，课后作业

1，1901. 寻找峰值

在这里插入图片描述

暴力解法，若走到一个格子都与周围四个比较，然后选择最大的，最后一定能走到一个峰顶
基于上面的思路，考虑使用二分
先得到某一行的最大值，一该最大值为基础，和上下两行的相邻元素进行比较，分类讨论：
易证得：数值大的元素的那边区间一定会存在一个峰顶（具体分析如下）
在这里插入图片描述

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        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 # left 循环不变量
        return [left, mat[left].index(max(mat[left]))]

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

在这里插入图片描述

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 2
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == nums[right+1]: # 和区间最后一个元素比较
                right -= 1
            elif nums[mid] < nums[right+1]:
                right = mid - 1
            else:
                left = mid + 1
        return nums[left]