二分查找

二分搜索

从今天开始使用另一种刷题方式和记笔记方式，按照刷题笔记的模块划分把一类题刷明白，并且按照模块总结笔记总结经验，还要保证不断复习！

一.最基础的二分查找

先粘代码，查找某个数都是这个格式

#include <vector>
using namespace std;
class Solution {
public:
    int search(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){
                return mid;
            } else if(nums[mid]<target){
                left=mid+1;
            } else{
                right=mid-1;
            }
        }
        return -1;
    }
};

有两个点是需要注意，容易犯错的

1.while循环中的条件

在上面的代码中while循环里的条件是left<=right，而不是left<right的原因是如果使用left<right当left和right相等时，比如left=right=2，会跳出循环，这样就漏掉了这个数。因此要谨记是小于等于。

2.left=mid+1 right=mid-1

这里更新left和right的值没有使用left=mid,right=mid的原因是，我们进入循环的第一个if判断已经判断出mid不是我们的target了，所以在后续的更新中不需要从mid开始，而是从mid-1,mid+1开始。

3.其他tips

有一个要知道的前提是我们搜索的范围是[left,right]，全闭区间，所以left=0，right=nums.size()-1

另外还有一个点很容易忽略，就是在上面的代码中定义mid时使用的是int mid=left + (right - left) / 2 ;而不是int mid=(left+right)/2;。这里是一个很细微的细节，因为测试用例中可能会有范围非常大的情况，大到left+right超出int的范围溢出，而上面的这种写法很好的避免了溢出，并且结果与int mid=(left+right)/2;相同。

总结：定义left,right，while循环，定义mid，判断mid，根据nums[mid]与target大小更新left和right

注意：1.while里写left<=right2.left=mid+1.right=mid-1

二、二分查找寻找左侧边界

在有些情况下，并不是找到目标值的索引就够了，比如有序数组nums=[1,2,2,2,3],target为3，此时我想得到target的左侧边界，上面的算法就不奏效了，需要改进。

先粘代码

int binarysearch(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;
        } else if(nums[mid]>target){
            right=mid-1;
        } else{
            right=mid-1;//收缩右侧边界
        }
    }
  if(left>nums.size()-1||nums[left]!=target)
        return -1;
    return left;
}

while循环里的条件和当nums[mid]<target，nums[mid]>target时更新left和right的方式不变，唯一发生改变的是当nums[mid]=target时不会返回mid，而是right=mid-1更新right，收缩右侧边界。

这段代码跳出循环的条件依旧是left==right+1，有以下四种情况：①当数组中存在target时，right=mid-1会使right的值等于left-1，跳出while循环；②当nums中所有数都小于target，最终left=num.size()，跳出while循环；③当nums中所有数都大于target，最终right=-1，跳出while循环；④当target不存在但是nums中有比它大和小的数时，此时的left等于nums中小于target的个数（这是一个很重要的特性）。

所以跳出循环后要根据left的值判断是哪种跳出循环的情况。若left>=nums.size(),表示nums中所有数都小于target，对应第②种情况；若nums[left]!=target表示left没有移动或者移动了却没有找到target，对应第③④种情况；这两种都不是说明已经找到了target的左侧边界，返回left；

总结：在二分查找基础上，修改当nums[mid]==target时执行的语句为right=mid-1，以此来收缩右侧边界，并且在跳出循环后要判断left>nums.size()-1||nums[left]!=target，都不符合才返回-1。
此外，当nums中没有target时，left代表了nums中大于target的个数！！

注意：记得当nums[mid]==target时执行的语句为right=mid-1，记得最后要判断left的值，看有没有移动到大于nums.size()-1的地方，或者没有移动（通过nums[left]!=target来判断），最后再返回left

三、二分查找寻找右侧边界

跟查找左侧边界类似，只需要修改几个地方

int binarysearch(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;
        } else if(nums[mid]>target){
            right=mid-1;
        } else{
            left=mid+1;//收缩左侧边界
        }
    }
  if(right<0||nums[right]!=target)
        return -1;
    return right;
}

跳出while循环只有三种情况，与寻找左侧边界时类似

注意：在寻找左侧边界的基础上记得改成left=mid+1收缩左侧边界，跳出循环后条件也变成了判断right,right<0||nums[right]!=target

练习：

二分查找寻找左侧边界和右侧边界

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

我们很简单的先找左侧边界再找右侧边界就可以了

class Solution {
public:
    int binarySearchLeft(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){
                right=mid-1;
            } else if(nums[mid]<target){
                left=mid+1;
            } else if(nums[mid]>target){
                right=mid-1;
            }
        }
        if(left>nums.size()-1||nums[left]!=target)
            return -1;
        return left;
    }
    int binarySearchRight(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;
            } else if(nums[mid]<target){
                left=mid+1;
            } else if(nums[mid]>target){
                right=mid-1;
            }
        }
        if(right<0||nums[right]!=target)
            return -1;
        return right;
    }


        vector<int> searchRange(vector<int> &nums, int target) {
            if(nums.size()==0)
                return{-1,-1};
            return {binarySearchLeft(nums,target), binarySearchRight(nums,target)};
        }

};

二分查找寻找左侧边界中left含义的应用

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

善用left含义的定义，代表的含义是nums中大于target的个数

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;
            }else if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]==target){
                right=mid-1;
            }
        }
        return left;
    }
};

四、二分搜索问题的泛化

传统的二分搜索算法解决的是在有序数组中寻找某个值的下标或者左右界，但是除了这种问题，二分搜索还能进行泛化，转变为解决：

一个自变量x，一个关于x的函数f(x)，一个目标值target。
并且题目要求满足：
1.f(x)必须是x上的单调函数
2.题目要求f(x)==target时x的值

接下来以力扣857题为例

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

这里我们比较容易的看出target就是H，x应该是K，则我们需要构造一个函数F(x)来与target比较，那么这个函数应该是求根据速度求时间的函数，上代码

#include <vector>
#include "algorithm"
using namespace std;

class Solution {
public:
    //建模，x为进食速度，F(x)为计算进食所需时间的函数，target就是给我们的时间H
    int f(int x,vector<int>& piles){
        int time=0;
        for(int i=0;i<piles.size();i++){
            time+=piles[i]/x;
            if(piles[i]%x!=0)
                time++;
        }
        return time;
    }
    int minEatingSpeed(vector<int>& piles, int h) {
        int max=0;
        for(int i=0;i<piles.size();i++){
            if(piles[i]>max)
                max=piles[i];
        }
        //这里left和right的取值要进行考虑，left和right应该是速度，最小应该为1，最大应该为piles中的最大值，因为一次吃一堆，再大也没有用了
        //但是取最大值要进行计算，或者直接取piles数组中数字取值的最大值，根据题意可以得知是10000
        int left=1,right=max;
        while (left<=right){
            int mid=left+(right-left)/2;
            if(f(mid,piles)<h)
                right=mid-1;
            else if(f(mid,piles)>h)
                left=mid+1;
            else
                right=mid-1;
        }
        return left;
    }
};

另一道题目也是类似的思路

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

套路都是类似的，只不过每次求left和right时需要思考一下

#include <vector>

using namespace std;
class Solution {
public:
    //建模，target为days，x应该为运载能力，f(x)为求某运载能力所需的时间
    int f(int x,vector<int>& weights){
        int days=0;
        for(int i=0;i<weights.size();){
            int cap=x;
            while (i<weights.size()){
                if(cap<weights[i])
                    break;
                else{
                    cap-=weights[i];
                    i++;
                }
            }
            days++;
        }
        return days;
    }

    int shipWithinDays(vector<int>& weights, int days) {
        int max=0,sum=0;
        for(int i=0;i<weights.size();i++){
            sum+=weights[i];
            if(max<weights[i])
                max=weights[i];
        }
        //上下界如何选取？下届应该是weight中的最大值，因为每次必须带走一件货物，所以下届应该是最大值，最大载重就是一次将weight中所有货物带走，因此是weight中所有重量之和
        int left=max,right=sum;
        while (left<=right){
            int mid=left+(right-left)/2;
            if(f(mid,weights)>days)
                left=mid+1;
            else if(f(mid,weights)<days)
                right=mid-1;
            else
                right=mid-1;
        }
        return left;
    }
};

注意，这种方法虽然方便记忆，但是效率上不是很高，在力扣上执行的速度偏慢，如果可以的话，还是去学下题解中由二分搜索转为判定问题的方法。