二分法

引入

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n=nums.size();
        vector<int>sum={0,nums[0]};
        for(int i=1;i<n;i++){
            sum.push_back(sum[i]+nums[i]);
        }
        int minLen=n,flag=0;
        for(int i=0;i<=n;i++){
            int r=n,l=1;
            while(l<=r){
                int m = r - (r-l)/2;
                if(sum[m]-sum[i]>=target){
                    r=m-1;
                }else
                    l = m+1;
            }
            if(l<=n){
                minLen = min(minLen,l-i);
                flag =1;
            }
        }
        if(flag)
            return minLen;
        return 0;
    }
};

以此题为引入，笔者发现对于二分法的熟练程度很差，决心搞清楚二分法的细节

~~也就是说上面的代码虽然能AC，但其实是错误案例~~

首先，二分法的循环终止条件最好是left < right, 因为这有利于在left == right的时候退出循环。
这并不会导致left大于right，因为无论是left和right，值的改变依赖于middle = left+ (right - left)/2，因此不可能突变到外面，相等时必然退出。

其次，笔者捋不清楚在二分法结束后，得到的$left$或$right$是非严格单调序列中的下界，上界还是target区间中的任意值，也不清楚如果target不存在，返回的是大于target的坐标还是小于target的坐标。

实际上，在一些算法竞赛书中，它们被叫做前驱和后继，而笔者认为它们的区别和STL标准库中的$upper_bound$与$lower_bound$作用类似，因此更愿意称其为目标的下界与上界。

需要提前表明的是，即使C++提供了对于整数的二分查找，我们学习二分查找仍然有很强的意义，因为很多时候并不是严格的从给定序列中返回对于target的查找结果，而是融入其他算法之中。

例如，我们可以将求最优解问题转化为在给定区间进行二分查找测试可行性的问题，此类问题机械地调用STL库完成是比较困难的。

现在，让我们开始吧

二分查找例题

表明一下笔者对于洛谷和力扣的态度：洛谷更考验综合能力，力扣更锻炼单个算法的能力。因此初期学习某个特定算法可以使用力扣。

力扣704. 二分查找

在这道题目中，我们实现了一个严格单调序列中的二分查找
这是一个比较简单的事情

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0,right = nums.size()-1;//定义左闭右闭区间
        while(left<right){
            int middle = left + (right-left)/2;//向下取整的mddle
            if(nums[middle]>=target)
                right = middle;
            else
                left = middle+1;//缩小区间避免死循环，因为是向左取整，所以left+1
        }//有target时，right停留在target处，left去逼近target
        //没有target时，right停留在比target大的第一个数，left去逼近
        //所以right或者left的坐标是target的左前驱
        return nums[right]==target?right:-1;
    }
};

力扣34. 在排序数组中查找元素的第一个和最后一个位置

在这道题目中，我们需要面对一个非严格递增的序列。

我们可能遇见target有n个，此时二分查找函数需要区分出找上界还是找下界

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int right = nums.size()-1,left=0;
        if(nums.size()==0)
            return{-1,-1};
        while(right>left){
            int m = left +(right - left)/2;//向下取整
            if(nums[m]>=target)//大于等于取左区间，找下界
                right = m;
            else
                left =  m+1;//由于是left去主动逼近right，因此最后得到的下标以right优先。是下界或大于target的第一个下标
        }
        int low = nums[left] ==target?left:-1;
        right = nums.size()-1,left=0;
        while(right>left){
            int m = left +(right - left)/2 + 1;//向上取整，所以要right去找left
            if(nums[m]>target)//大于等于取左区间，找上界
                right = m-1;
            else
                left =  m;
        }
        int up = nums[right] == target?right:-1;
        return {low,up};
    }
};

力扣33. 搜索旋转排序数组

STL中的二分查找

lower_bound()和upper_bound储存在STL库中的头文件<algorithm>中，能且只能对有序容器使用

我们先来看一个正常对升序容器使用的例子

#include<map>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    vector<int> a1 = {1,2,4,6,7,8,8,8,8,9,9,10,15};
    vector<int> a2 = {8,8,6,5,4,4,3,1};.
    auto left = lower_bound(a1.begin(),a1.end(),8);
    auto right = upper_bound(a1.begin(),a1.end(),8);
    cout<<"left_index = "<<left - a1.begin()<<endl;
    cout<<"right_index = "<<right - a1.begin()<<endl;
    return 0;
}

输出：

1 2	left_index = 5 right_index = 9

可以看出，在默认升序排序的容器中，lower_bound()和upper_bound遵循以下规则：

默认排序规则是升序，即 a < b
lower_bound()返回第一个不满足 a < value 条件的迭代器
upper_bound()返回第一个满足a > value条件的迭代器

在严格升序容器里面，lower_bound指向唯一满足 a == value的元素，而upper_bound则指向其下一位
在非严格升序容器里面，lower_bound指向满足a == value的区间左侧，upper_bound指向这个区间的下一位。
即区间[lower_bound(),upper_bound)恰是所有value的位置，这就是上下界的由来

那么，如果是降序容器呢？

我们可以向其传入自定义的比较函数，仍然能得到类似的结果，其机理在于：

默认排序规则是升序，即 a > b
lower_bound()返回第一个不满足 a > value 条件的迭代器
upper_bound()返回第一个满足a < value条件的迭代器

#include<map>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    vector<int> a1 = {1,2,4,6,7,8,8,8,8,9,9,10,15};
    vector<int> a2 = {8,8,6,5,4,4,3,1};
    auto left = lower_bound(a2.begin(),a2.end(),8,greater<int>());
    auto right = upper_bound(a2.begin(),a2.end(),8,greater<int>());
    cout<<"left_index = "<<left - a2.begin()<<endl;
    cout<<"right_index = "<<right - a2.begin()<<endl;
    return 0;
}

输出：

1 2	left_index = 0 right_index = 2

关于STL二分查找边界

1 2	vector<int> v = {1, 3, 3, 5, 7};

查找值	`lower_bound` 返回位置	`upper_bound` 返回位置
0	index 0 → `1`	index 0 → `1`
3	index 1 → `3`	index 3 → `5`
4	index 3 → `5`	index 3 → `5`
7	index 4 → `7`	index 5 → end()
10	index 5 → end()	index 5 → end()

如果value不在里面，会返回第一个大于等于或大于的元素的迭代器，如果没有满足条件的，就返回end()

1498.满足条件的子序列数目

#include<algorithm>
class Solution {
public:
    const int MOD = 1e9+7;
    int arr_2[100005]={1,2};
    int numSubseq(vector<int>& nums, int target) {
        const int length = 1e5;
        for(int i=2;i<=length;i++){
            arr_2[i] = (arr_2[i-1]*2)%MOD;
        }
        std::sort(nums.begin(),nums.end());
        int res = 0;
        for(int i=0,size = nums.size();i<size;i++){
            int min_index = i;
            int max_index = upper_bound(nums.begin()+i,nums.end(),target-nums[i])-nums.begin()-1;
            //这里会返回第一个大于target-nums[i]的下标，然后-1，就是在搜索域内全部满足<=target-nums[i]元素的右闭界
            if(max_index<min_index)
                continue;
            res += arr_2[max_index-min_index];
            res %=MOD;
        }
        return res;
    }
};

倍增法

二分法的逆运算，不断乘二寻找目标区间

前缀和与差分

一维前缀和/差分

一维前缀和指的是在一维序列中前n项的和
差分指的是前后两项差组成的新序列。
前缀和与差分被认为是互逆的运算。

前缀和可以在O(1)时间输出给定序列的区间和
差分可以在O(1)时间修改某个序列的区间值

但它们都有自己的局限性。

#include<iostream>
#include<vector>
using namespace std;
const int MAXN=1e5+5;
int main(){
    int n;
    cin>>n;
    while(n){
        int D[MAXN]={};
        for(int i=0;i<n;i++){
            int l,r;
            cin>>l>>r;
            D[l]+=1;
            D[r+1]-=1;//因为需要操作区间是[l,r]，r+1保证右区间也是闭合的
        }
        int m=0;
        for(int i=1;i<=n;i++){
            m+=D[i];
            cout<<m<<" ";
        }
        cin>>n;
    }
    return 0;
}

#include <iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100005;
int n,m;
long long city[MAXN][4],route[MAXN];//route[i]表示从i到i+1坐了多少次
int D_route[MAXN];//d[i] = sum[i] - sum[i-1]
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>route[i];
    }
    for(int i=1;i<n;i++){
        cin>>city[i][1]>>city[i][2]>>city[i][3];
    }
    int left,right;
    for(int i=1;i<=m-1;i++){
        left = min(route[i],route[i+1]),right = max(route[i],route[i+1]);
        D_route[left]++;
        D_route[right]--;
    }
    long long ans=0;
    for(int i=1;i<n;i++){
        route[i]=D_route[i]+route[i-1];
        ans+= min(route[i]*city[i][1],route[i]*city[i][2]+city[i][3]);
    }
    cout<<ans;
    return 0;
}