当前位置：首页 > article >正文

二分法篇——于上下边界的扭转压缩间，窥见正解辉映之光（2）

article 2024/12/5 10:06:16

在这里插入图片描述

前言

上篇介绍了二分法的相关原理并结合具体题目进行讲解运用，本篇将加大难度，进一步强化对二分法的掌握。

一. 寻找峰值

1.1 题目链接：https://leetcode.cn/problems/find-peak-element/description/

1.2 题目分析:

题目要求返回数组内任一峰值元素的下标
时间复杂度要求为log n，排除暴力解法直接遍历的可能.
峰值元素：大于其左右相邻元素的元素。

1.3 思路讲解：

题目给出提示，可以假设nums[-1]=nums[n]=负无穷，且要求时间复杂度为log n，因此可考虑寻找二段性利用二分法求解。
寻找⼆段性：
任取⼀个点 i ，与下⼀个点 i + 1 ，会有如下两种情况：
• arr[i] > arr[i + 1] ：此时「左侧区域」⼀定会存在⼭峰（因为最左侧是负⽆
穷），那么我们可以去左侧去寻找结果；
• arr[i] < arr[i + 1] ：此时「右侧区域」⼀定会存在⼭峰（因为最右侧是负⽆
穷），那么我们可以去右侧去寻找结果。
当我们找到「⼆段性」的时候，就可以尝试⽤「⼆分查找」算法来解决问题。

1.4 代码实现：

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int mid=left+(right-left+1)/2;
            if(nums[mid]>nums[mid-1])
            {
                left=mid;
            }
            else
            {
                right=mid-1;
            }
        }
        return left;

        
    }
};

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

2.1 题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/

2.2 题目分析：

现有一个按照升序排列，且元素值各不相同的数组，每旋转一次，即为把数组原先末尾的值调向第一个
将该数组旋转数次后，要求返回此时数组内的最小元素
时间复杂度为log n

2.3 思路讲解：

旋转后的数组满足下图情形，其中A，B，C，D均为数组按下标顺序所对应的值，且C即为所求。
在这里插入图片描述
以D为界限，A-B内全都大于D，C-D内全都小于D，满足二段性，因此可考虑使用二分法求解，具体步骤如下：

令left=0，right=nums.size()-1,target=nums[right]，其中target即为上图中的D
求取中点mid=left+(right-left)/2，如果nums[mid]>target，说明mid此时位于AB区间内，需要更新left=mid+1
如果nums[mid]<target，说明mid此时位于CD区间内，需要更新right=mid
while循环二分，最终nums[left]即为所求。

2.4 代码实现：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left=0,right=nums.size()-1;
        int target=nums[right];//靶区间
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]>target)
            {
                left=mid+1;
            }//更新left
            else
            {
                right=mid;
            }//更新right
        }
        return nums[left];
    }
};

三. 搜索插入位置

3.1 题目链接：https://leetcode.cn/problems/search-insert-position/description/

3.2 题目分析：

题中给出一个升序数组和target，要求查找target在数组内的位置
如果target不存在，则返回其应该插入的位置
时间复杂度为logn

3.3 思路讲解：

时间复杂度为logn，且满足二段性，因此可考虑使用二分法解决，具体步骤如下：

令left=0，right=nums.size()-1,分别作为左右区间
求取中点mid=left+(right-left)/2，如果nums[mid]<target，说明[left,mid]内的所有元素均小于target，将left更新为mid+1
如果nums[mid]>t=arget,说明[mid,right]内所有元素均大于等于target，将right更新为mid.
while循环二分，最终left=right，此时，如果nums[left]<target，说明数组内所有元素均小于target，需要在末尾插入，返回left+1
反之则正常返回left即可

3.4 代码实现：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]<target)
            {
                left=mid+1;
            }//更新left
            else
            {
                right=mid;
            }//更新right
        }
        if(nums[left]<target)
        {
            return left+1;
        }
        return left;
        
    }
};

四. 点名

4.1 题目链接：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/

4.2 题目分析：

数组内有n个元素，代表0-n，但其中缺少了0-n中的一个元素，返回该值

4.3 思路讲解

该题方法多样，可以采取异或法，总和累减法等方法解答。由于本篇主题为二分法，因此只讲解二分法如何解答该题。
二分法的重点为二段性：

观察可知，假设缺失元素为target
在target左侧，[left,target]内，每一个元素的值对应其下标
在target右侧，[target,right]内，每一个元素的值都比其下标大1
因此该题二分法具体步骤如下：

令left=0,right=nums.size()-1，作为左右边界

求取中点,mid=left+(right-left)/2，如果nums[mid]=mid,则更新left=mid+1

如果nums[mid]>mid,更新right=mid

while循环二分后，right即为所求
需注意一种特殊情况，当right=nums[right]时，说明缺失的数字为n，[left,right]内所有元素均有下标一一对应，此时需要返回right+1

4.4 代码实现

class Solution {
public:
    int takeAttendance(vector<int>& records) {
         int left=0,right=records.size()-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(records[mid]==mid)
            {
                left=mid+1;
            }//更新为left
            else
            {
                right=mid;
            }//更新right
        }
        if(records[right]==right)
        {
            return right+1;
        }//缺少的元素为n
        else
        {
            return right;
        }
        
    }
};