好像看起来效果不是很好，先放这。

二分分为二分查找和二分答案。

二分查找

二分查找，是用来在一个有序数组中查找某一元素的算法。

具体步骤与一个游戏数字炸弹类似。

数字炸弹

当然，如果你运气很好的话，随便猜，说不定一次就猜中了。但是如果你的运气很差呢？我们要怎么样去做，来使得即便我们运气很差，也能尽可能的去得到更好的分数呢？

我们可以发现，只要我们每一次都去猜位于区间中间的数字，那么我们每一次都可以让询问的区间长度缩短一半。（不管猜大了还是猜小了）然后我们只要重复使用这个策略，一直到猜中即可。

上面这个在运气最不好的情况下显然是最优的，因为每一次不管猜大了还是猜小了都至少能将询问区间缩短一半。而其他的方法，如果某次运气不好，那么询问区间缩短就不如一半。

按照上面的过程，我们每次可以将区间长度缩短一半，一直到最后区间长度为1，即表示我们找到了。我们可以列个式子来看看我们最多需要找几次，假设我们找了$x$次，反过来算，每次区间长度增加一倍。
$$2^{x} \geq 100 \implies x\geq \log_{2}100$$
也就是说，如果询问的区间长度为$n$，那么我们最多只要找$\log_{2}n$次即可找到我们想要的答案。
带入个具体的数字 $n=10^6$ ,$\log_{2}n=20$ (近似值)，也就是说，我们本来最多可能要找1000000次，但是用这个方法就只要找20次。可以说是质的飞跃。

过程

那么回到二分查找来，如果我们想在一个排好序的数组里面找到某一个数，只需要用和上面同理的过程就好了。

即：如果是个单调递增的，如果中间元素小于，那么就往右侧找，反之则往左侧找。

查询次数最坏为$\log n$

这个过程应该很好懂，那代码要怎么写呢？通常数组中会有重复的数字，我们想找的可能是第一个大于等于某个数字的第一个数（或者位置），也可能是第一个小于等于某个数字的第一个数（或者位置）。这两者都差不多。

int find1(int x) {//找第一个大于x的元素位置
    int l = 1, r = n;  // 初始化左右指针，l为1，r为n，假设n为数组的长度
    while (l < r) {  // 当l小于r时继续二分查找
        int mid = (l + r) / 2;  // 计算中间位置
        if (a[mid] <= x)  // 如果a[mid]小于等于x，说明答案在mid右边
            l = mid + 1;  // 更新l为mid+1
        else  // 如果a[mid]大于x，说明答案等于mid或者在mid左边
            r = mid;  // 更新r为mid
    }
    return l;  // 返回l，即第一个大于x的元素位置
}

初始区间：[l ................. r]

mid = (l + r) / 2  // 向左偏中间点，避免死循环

若 a[mid] <= x：
    [     mid+1 ........... r]   ← 答案在右边（丢弃 mid）
否则：
    [l .......... mid]           ← 答案可能在左边（保留 mid）

直到 l == r：
    l 就是第一个 > x 的元素的位置

int find2(int x) {//找小于x的最大的的元素位置
    int l = 1, r = n;  // 初始化左右指针，l为1，r为n，假设n为数组的长度
    while (l < r) {  // 当l小于r时继续二分查找
        int mid = (l + r + 1) / 2;  // 计算中间位置，偏向右边，防止死循环
        if (a[mid] >= x)  // 如果a[mid]大于等于x，说明答案在mid左边
            r = mid - 1;  // 更新r为mid-1
        else  // 如果a[mid]小于x，说明答案等于mid或者在mid右边
            l = mid;  // 更新l为mid
    }
    return l;  // 返回l，即第一个小于x的元素位置
}

初始区间：[l ................. r]
                ↑     ↑
              mid     r

mid = (l + r + 1) / 2  // 向右偏中间点，避免死循环

若 a[mid] >= x：
    [l ........ mid-1]           ← mid太大，往左走（丢弃 mid）
否则：
    [mid ............ r]         ← mid是可行解，往右收缩

直到 l == r：
    l 就是最后一个 < x 的元素的位置

可以发现mid的取值在两个代码里不一样，那么为什么会不一样呢？

这其实与l和r的更新部分有关。加1或者不加1是为了避免死循环，也就是说当l=r-1的时候，当区间长度刚好为2的时候。

如果
mid=(l+r)/2;
l=1,r=2时,mid=1
而此时万一 l=mid,那么l又变回了1，那么就死循环了
另一种同理。

所以我们只需要写完代码后看看代码里是l=mid还是r=mid，然后mid的取值避开死循环的情况即可。

那么上面就是二分查找的代码和过程详解了，如果还有哪里有问题，就照着步骤再试一试吧。

常见题目

某个数第一次出现的下标

输入 $n$ 个不超过 $10^9$ 的单调不减的（就是后面的数字不小于前面的数字）非负整数 $a_1,a_2,\dots,a_{n}$，然后进行 $m$ 次询问。对于每次询问，给出一个整数 $q$，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 $-1$ 。

很显然，假设我们要找$x$，我们只需要用二分找到第一个大于等于$x$的数的下标即可。

某个数出现的次数

给你 $n$ 个数字，问你某个数字出现多少次。

如果数字的大小范围小于$10^{7}$的话，我们直接开个计数数组存一下这个数出现的次数即可。（即计数排序）

如果数字的大小范围很大的话，我们就不能这么做了，我们得想想有没有什么方法。

方法：

将数组排序，排序后，该数$x$出现的次数就是
$$最后一个x的下标-第一个x的下标+1$$
例如

a   = {1 3 3 3 3 4 5 6}
下标 = {1 2 3 4 5 6 7 8}

那么3这个数字在a里面出现了$4$次，也就是$5-2+1=4$
本来需要遍历整个数组a，现在是需要两次二分即可,复杂度从$O(n)$ 到了$O(\log n)$

上一个问题的扩展

给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A – B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。数列中数的个数$\leq 2\times 10^5$

暴力的思路肯定就是枚举每个数当A，再枚举每个数当B，看看A-B是否等于C，等于的话就给答案个数+1，即
$$\sum_{i=1}^{n}\sum_{j=1}^{n}(a_{i}-a_{j}==C)$$
很显然这是$O(N^{2})$的。

我们可以发现，当我们枚举A的时候，实际上B这个数字已经确定出来了，因为$B=A-C$，所以我们只需要找到原数组里有多少个数字等于$A-C$就可以了。

而找到原数组中某个数字出现了多少次，就是上一题的内容。

过程就变成了
$$\sum_{i=1}^{n}((C-a_{i})出现的次数)$$
那么总的复杂度就变成了$O(n\log n)$

这个套路经常会用在枚举个数的时候来帮助我们优化。

STL

二分也是在标准库里面有函数可以直接调用的

int n;
int a[N];

int x;

int id=lower_bound(a+1,a+1+n,x)-a; // 数组下标从1开始，找到的是第一个大于等于x的数的下标
int id=lower_bound(a,a+n,x)-a; // 数组下标从0开始

int id=upper_bound(a+1,a+1+n,x)-a; //找到的是第一个大于x的数的下标
int id=upper_bound(a,a+n,x)-a;

vector<int> a(n);
int id=lower_bound(a.begin(),a.end(),x)-a.begin();

vector<int> a(n+10);
int id=lower_bound(a.begin()+1,a.begin()+1+n,x)-a.begin();

//upper_bound同理

二分答案

解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了「二分答案」。

例题

解题过程

乍一看，好像没什么解题思路。

直接找到设定的高度需要是多少好像比较困难

但是如果我们已经设定好了一个高度，想知道这个高度能砍多少米的木材，这个是比较简单的，我们只需要$O(n)$的遍历一遍就好了。

同时我们可以发现，高度越低，那么木材数量也就越多，而高度越高，那么木材数量也就越少。

也就是说，假设我们开了一个数组$h$，$h_{i}$表示当高度为$i$时，能砍下的木材数量。

我们要找的答案也就是对于$h$这个降序的数组里，最后一个$>M$的数的下标。

那么我们直接二分即可。

由于我们二分的时候只会用到部分位置上的数字，所以我们不需要提前把这个$h$数组中的每个数都求一遍，只需要在二分检查的时候把它求出来再进行比较即可。

时间复杂的为$O(n\log n)$

具体看代码:

#include<bits/stdc++.h>

using namespace std;

constexpr int N=1e6+10;

int n,m;
int a[N];

long long check(int x){
    long long res=0;
    for(int i=1;i<=n;i++){
        res+=max(0,a[i]-x);
    }
    return res;
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int l=0,r=4e5;
    while(l<r){
        int mid=(l+r+1)/2;
        if(check(mid)>=m) l=mid;
        else r=mid-1;
    }
    cout<<l<<'\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

总结

如何把二分答案与数组上的二分查找联系起来？

假设范围是 [2,3,4,5]，我们相当于在一个虚拟数组 [check(2),check(3),check(4),check(5)] 中二分找第一个（或者最后一个）值为 true 的 check(i)。

常见题型

1 求满足某种条件的最大值/最小值

即例题的形式

2 最小化最大值/最大化最小值

例如：

同样的，我们无法很好的直接确认答案是多少。

但是我们可以发现，如果我们限制每一段的和最大是$x$，并且我们在分段的时候，尽可能把每一段都塞满。

$x$越大，那么分段后，段数会变小

$x$越小，那么分段后，段数会变大

这里节约篇幅，不列例子，可以尝试着自己举例一下。

然后题目就转变成和上面例题一样的问题了。我们只需要二分这个最大的和即可。

3 第K大/小的数

$第 k 小等价于：求最小的 x，满足 <= x 的数至少有 k 个（k 从 1 开始）$

$第 k 大等价于：求最大的 x，满足 >= x 的数至少有 k 个（k 从 1 开始）$

很显然，直接暴力的求，不管是空间还是时间都是肯定不够的。

我们来看看二分答案在这里的思路。

我们假设答案是 $x$。

我们如果想找在原数组有几组$(A+B\leq x)$的，要怎么找？

如果问你有几组$(A+B==x)$的，你会做吗？实际上这一题与上面的找$(A-B=C)$的个数是一样的。

那么$A+B\leq x$也同理，可以枚举A，二分出有几个B满足这个条件。

然后我们就可以找到$\leq x$的数的个数了

然后，我们想找得是第K小的数字，也就等价于$求最小的 x，满足 <= x 的数至少有 k 个（k 从 1 开始）$

可以发现x越大，<=x的数越少，x越小，<=x的数越多，所以这部分我们也可以直接二分求解。

类似题目：
ABC155d

4 中位数相关

中位数指的是数组排完序后位于中间的数，其实与求第$K$大的数是一样的，只不过它求得是第$\frac{n+1}{2}$大的数字。

总结

二分是个很常用的算法，二分查找时我们只需要调用STL库里面的函数即可，二分答案的重点则是check函数的处理。