【二分查找】Leetcode例题

【1】69. x 的平方根 - 力扣（LeetCode）

🍡解题思路：首先想到的是暴力查找，从1开始依次比较x与num*num的大小，然后找出满足num*num<=x且(num+1)*(num+1)>x的num值；再来看看能不能优化一下，因为是有序的比较，因此可以考虑使用二分查找算法来解决此题。

🍡算法原理：首先找出二段性，观察发现，所求出算数平方根只保留整数部分，因此可以将结果值划分到左段，将num*num<=x的划分为一段，num*num>x的划分为另一段，根据我之前发过的二分查找算法模板介绍的博客(【二分查找】模板+例题)，可以发现这就是典型的查找右端点的二分查找算法，找出条件判断语句的判断条件即可求解

🍡解题步骤：

1）定义左右边界left,right

2）定义循环判断条件left<right

3）设置mid值，由于是右端点二分查找算法，因此是mid=left+(right-left+1)/2（不清楚为什么的可以看看【二分查找】模板+例题）

4）编写条件判断语句：

1.若mid*mid<=x,left=mid

2.若mid*mid>x,right=mid-1

细节处理：由于题目是从0开始的，因此小于1的

注意：由于题目给出的数字范围太大，可能会出现溢出情况，因此mid用longlong类型，left和right也可以设置成longlong类型；

🍡实现代码：

    int mySqrt(int x) {if(x<1)return 0;int left=1;int right=x;while(left<right){long long mid=left+(right-left+1)/2;if(mid*mid<=x){left=mid;}else if(mid*mid>x){right=mid-1;}}return left;}

【2】35. 搜索插入位置 - 力扣（LeetCode）

🍡解题思路：首先想到暴力查找，依次比较nums[i]与target的大小，如果nums[i]>=target那么就输出对应位置下标，但是题目要求时间复杂度为O(logN)，因此考虑使用二分查找算法解决

🍡算法原理：可以发现数组的二段性，将数组划分为x<target和x>=target两部分，要求解包含在x>=target部分，很明显是寻找左端点的二分查找

🍡解题步骤：

1）定义左右边界left,right

2）定义循环判断条件left<right

3）设置mid值，由于是左端点二分查找算法，因此是mid=left+(right-left)/2

4）编写条件判断语句：

1.若nums[mid]<target,left=mid+1

2.若nums[mid]>=target,right=mid

细节处理：如果target的值比nums中所有元素都要大，插入位置就是nums.size()，即nums的下一个位置的下标；如果不单独写，输出的就是nums最后一个位置下标，是错误的。

🍡实现代码：

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

 【3】852. 山脉数组的峰顶索引 - 力扣（LeetCode）

🍡解题思路：题目要求的峰值元素，比左右两侧的元素都要大，因此可以通过比较相邻元素的大小来确定峰值元素位置

🍡算法原理：寻找二段性，会发现峰值左侧元素都是比它下一个元素小，峰值右侧（包含峰值在内）都是比它下一个元素大；这样就划分出了二段性，会发现是寻找左端点的二分查找算法。

（同理，也可以通过将当前元素与上一个元素比较，将峰值划分在左侧，通过寻找右端点的二分查找算法求解）

🍡解题步骤：

1）定义左右边界left,right

2）定义循环判断条件left<right

3）设置mid值，由于是左端点二分查找算法，因此是mid=left+(right-left)/2

4）编写条件判断语句：

1.若arr[mid]<arr[mid+1],left=mid+1

2.若arr[mid]>arr[mid+1],right=mid

🍡实现代码：

    int peakIndexInMountainArray(vector<int>& arr) {int left=0;int right=arr.size()-1;while(left<right){int mid=left+(right-left)/2;if(arr[mid]>arr[mid+1]){right=mid;}else if(arr[mid]<arr[mid+1]){left=mid+1;}}return left;}

【4】162. 寻找峰值 - 力扣（LeetCode）

🍡解题思路：可以分为三种情况：

1、完全上升趋势

2、完全下降趋势

3、波折曲线

三种情况能找到峰值，因为nums的左侧趋向于-∞，右侧趋向于+∞；如果是情况1，那么最右侧元素就是峰值；如果是情况2，那么最左侧元素就是峰值；如果是情况3可以找到其中一个峰值。观察发现，若nums[i]>nums[i+1]，那么该值右侧呈现下降趋势，而nums最左侧趋向于-∞，因此该值左侧一定存在一个峰值；而当nums[i]<nums[i+1]，同理该值右侧一定存在一个峰值

🍡算法原理：通过上述分析，可以得到二段性，当nums[i]>nums[i+1]（包含峰值元素在内）时，向左搜索；当nums[i]<nums[i+1]时，向右搜索。因此可以使用左端点的二分查找算法

🍡解题步骤：

1）定义左右边界left,right

2）定义循环判断条件left<right

3）设置mid值，由于是左端点二分查找算法，因此是mid=left+(right-left)/2

4）编写条件判断语句：

1.若nums[mid]<nums[mid+1],left=mid+1

2.若nums[mid]>=nums[mid+1],right=mid

🍡实现代码：

    int findPeakElement(vector<int>& nums) {int left=0;int right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]>nums[mid+1])//找出二段性{right=mid;}else if(nums[mid]<nums[mid+1]){left=mid+1;}}return left;}

【5】153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

🍡解题思路：旋转之后变为两段升序数组，通过观察找到二段性，利用二分查找求解

🍡算法原理：可以发现旋转之后AB段的元素都比最后一个元素D的值大，而CD段元素（包含最小值在内）都比元素D的值小；因此划分出二段性。可以发现可利用左端点的二分查找求解

🍡解题步骤：

1）定义左右边界left,right

2）定义循环判断条件left<right

3）设置mid值，由于是左端点二分查找算法，因此是mid=left+(right-left)/2

4）编写条件判断语句：

1.若nums[mid]>nums[sz],left=mid+1

2.若nums[mid]<=nums[sz],right=mid

🍡实现代码：

    int findMin(vector<int>& nums) {int left=0;int right=nums.size()-1;int sz=nums.size();while(left<right){int mid=left+(right-left)/2;if(nums[mid]>nums[sz-1]){left=mid+1;}else{right=mid;}}return nums[right];}

【6】LCR 173. 点名 - 力扣（LeetCode）

🍡解题思路：可以求解的方式有很多，可以通过累加和的方式求解，也可以通过元素与下标待遇比的方式求解。同样也能用二分查找的方式求解

🍡算法原理：寻找二段性，可以发现缺失值左侧元素的下标值都和元素值相等，而右侧元素的下标值都和元素值不相等，因此根据这个特性划分出二段性

🍡解题步骤：

1）定义左右边界left,right

2）定义循环判断条件left<right

3）设置mid值，如果是右端点二分查找算法，因此是mid=left+(right-left)/2

4）编写条件判断语句：

1.若records[mid]==mid,left=mid+1

2.若records[mid]!=mid,right=mid

细节：右端点二分查找和左端点二分查找都行，要不就是插入元素左侧要不就是插入元素右侧，只需要最后返回的时候判断一下即可。可能存在records=[1,2,3]这种情况，定位在第一个元素;存在records=[0,1,2,3]这种情况，定位在最后一个元素的下一个；如果这两种情况单独考虑，那么使用右端点二分，就可以return left+1；而使用左端点二分，就可以return left-1;

为了方便起见，可以直接判断一下while结束之后在插入元素左侧还是右侧再来确定返回值即可

🍡实现代码：

    int takeAttendance(vector<int>& records) {int left=0;int right=records.size()-1;//找出二段性，缺失值左侧都是等于下标，右侧都是！=下标while(left<right){int mid=left+(right-left+1)/2;if(records[mid]!=mid)right=mid-1;elseleft=mid;}return left==records[left]?(left+1):left;//如果是缺失值左侧元素，left+1就是缺失值；如果是缺失值右侧元素，那么left就是缺失值}

    int takeAttendance(vector<int>& records) {int left=0;int right=records.size()-1;if(records[0]!=0) return 0;if(records[right]==right) return right+1;//找出二段性，缺失值左侧都是等于下标，右侧都是！=下标while(left<right)//左端点的二分{int mid=left+(right-left+1)/2;if(records[mid]!=mid)right=mid-1;elseleft=mid;}//return left==records[left]?(left+1):left;return left+1;}

    int takeAttendance(vector<int>& records) {int left=0;int right=records.size()-1;if(records[0]!=0) return 0;if(records[right]==right) return right+1;//找出二段性，缺失值左侧都是等于下标，右侧都是！=下标while(left<right)//右端点的二分{int mid=left+(right-left)/2;if(records[mid]!=mid)right=mid;elseleft=mid+1;}//return left==records[left]?(left+1):left;return left;}