二分法的总结

一、前言

最初始版的二分法是力扣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. 寻找峰值

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