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

在这里插入图片描述

前言

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

一. 寻找峰值

leetcodecnproblemsfindpeakelementdescription_5">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;}
};

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

leetcodecnproblemsfindminimuminrotatedsortedarraydescription_49">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;}//更新leftelse{right=mid;}//更新right}return nums[left];}
};

三. 搜索插入位置

leetcodecnproblemssearchinsertpositiondescription_89">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;}//更新leftelse{right=mid;}//更新right}if(nums[left]<target){return left+1;}return left;}
};

四. 点名

leetcodecnproblemsqueshideshuzilcofdescription_133">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;}//更新为leftelse{right=mid;}//更新right}if(records[right]==right){return right+1;}//缺少的元素为nelse{return right;}}
};