二分法的总结

本文主要是介绍二分法的总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、前言

最初始版的二分法是力扣704. Binary Search，而后面的二分法都是在这个基础上进行的变化

class Solution {
public:int search(vector<int>& nums, int target) {int left=0;int right=nums.size()-1;while(left<=right){//在这里选择的是左闭右闭的区间，左闭右开也是可以的int middle=(left+right)/2;//这里其实最好还是写成(right-left)/2+left，防止溢出if(nums[middle]==target){return middle;}else if(nums[middle]>=target){right=middle-1;//right是否能够等于middle-1还是要看自己写的区间是左闭右闭还是左闭右开}else{left=middle+1;}}return -1;}
};

其次，我开始刷了第二道求下标的题目力扣35. Search Insert Position，这道题我一开始想不懂为什么突然多了一个ret，为什么要用ret来记录下标，不能直接返回吗？什么时候要用ret来表示，什么时候又不用呢？这些问题在后面解答。

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left=0;int right=nums.size()-1;int ret=nums.size();while(left<=right){//这里依旧选择了左闭右闭的区间int middle=left+(right-left)/2;if(nums[middle]>target){ret=middle;right=middle-1;}else if(nums[middle]<target){left=middle+1;}else{return middle;}}return ret;}
};

再接下来就是力扣69. Sqrt(x)。这道题我就开始更蒙圈了，和704比起来，不仅要用ret来记录，而且if条件也变了，虽然我当时想到了要这样写，但是if else判断句直接给我干晕了，为什么这里只用两个判断句就行了呢？

class Solution {
public:int mySqrt(int x) {int left=0;int right=x;int ret;while(left<=right){//依旧使用左闭右闭区间int middle=left+(right-left)/2;if((long long)middle*middle<=x){ret=middle;left=middle+1;}else{right=middle-1;}}return ret;}
};

下一道是力扣153. Find Minimum in Rota，这是一道中等题，前面的都还是简单题，既然是中等题，当然比简单题要难，果然，我尝试用左闭右闭的区间都失败了，最后只能用左闭右开，到底什么时候用左闭右闭，什么时候不能用呢？由于这道题也没有target，我就想着应该是和left和right比，但并不明白是为什么？而且这道题怎么不用ret？为什么最后又要返回nums[left]？

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

下一道是力扣162. Find Peak Element，这道题也是中等题，果然我的边界条件就错得离谱，这道题又需要用到ret了。

class Solution {
public:int findPeakElement(vector<int>& nums) {auto get=[&](int i)->pair<int,int>{if(i==-1 || i==nums.size()){return {0,0};}else{return {1,nums[i]};}};int left=0;int right=nums.size()-1;int ret;while(left<=right){int middle=left+(right-left)/2;if(get(middle+1)<get(middle) && get(middle-1)<get(middle)){ret=middle;break;}else if(get(middle)<get(middle+1)){left=middle+1;}else{right=middle-1;}}return ret;}
};

下一道，力扣33. Search in Rotated Sorte，是旋转数组，在旋转数组中找target，我是直接不知道和二分法有什么关系了，最后从别人的题解里面发现可以找到left到middle的顺序或者right到middle的顺序，可是我做题目的时候怎么想得起来？为什么我联想不到？联想到了又会划分错边界条件。

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

下一道，744. Find Smallest Letter G。感觉这道题和69题很像，除了if判断句条件以及yijiretret需要一个初始值之外几乎没有差别

class Solution {
public:char nextGreatestLetter(vector<char>& letters, char target) {int left=0;int right=letters.size()-1;int ret=0;while(left<=right){int middle=left+(right-left)/2;if(letters[middle]>target){ret=middle;right=middle-1;}else{left=middle+1;}}return letters[ret];}
};

最后一题是力扣441. Arranging Coins，它这道题也是，我无法用左闭右闭的区间去写，而且也用到了等差数列求和的一个问题，我一开始也是想不到，而且关于left的初始值以及middle的值的设置也是有很多小坑。并且left居然不可以等于middle+1，会超时，而且最后返回的值居然变成了left？为什么？

class Solution {
public:int arrangeCoins(int n) {int left=1;int right=n;while(left<right){int middle=left+(right-left+1)/2;if((long long)middle*(middle+1)<=(long long)2*n){left=middle;}else{right=middle-1;}}return left;}
};

二、总结

相信大家在刷二分法的时候也会遇到一些相似的问题，接下来就一一解答吧

1.ret什么时候使用

这个其实就是去看题目的要求，如果说题目只是要找到target的下标，那么可以不需要用到额外的变量去存储，但如果需要让我们搜索插入位置，又或者说寻找峰值的话，如果不用变量去保存的话，很容易就会丢失上一个数据。这个还是比较好判断到底需不需要用ret。完全可以先写出大概的代码大纲之后进行细节补充，然后发现需要用一个变量保存的时候再去添加一个变量就好了。当然了，要注意变量的初始值，可以回去看看题目要求，尤其是边界条件。

2.什么时候不能用左闭右闭

用几个示例代入代码，看是否会发生死循环，如果会，就说明不能用left<=right当做while循环的条件

3.返回值到底怎么判断是什么

其实也可以把一个实例带入代码，看最后究竟哪一个才是题目要得到的值。多做几道题之后就会有感觉了。

4.边界条件，越界

5.left和right到底怎么写？怎么有时候是=middle，有时候又是middle+1的

（1）区间问题，看自己的区间是左闭右闭还是左闭右开

（2）或者也可以用实例带入代码

三、题目分类

1.普通二分查找，求下标（或者其数值）

        35. 搜索插入位置

        704. 二分查找

2.二分求最小

3.二分求最大

4.其他

        162. 寻找峰值

       

四、不同题目分类的解法（待续）

这篇关于二分法的总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---