二分法

什么是二分

二分即把问题折半来快速找到答案。例如以下的问题

已知$n$个数，分别为$a_1,a_2,a_3...a_n$，$a_i<=a_{i+1}$。
给出$x$，把$x$插入$a$中，使得$a$仍然有序，求$x$能插入的第一个位置。
数据范围：$1<=n<=10^5$

这是一道经典的二分题

这里讲一下二分查找的概念：

首先，我们知道答案肯定在$a_1$至$a_n$之间（废话+1）

然后，我们对最中间那个点进行判断，可以直接得出我们要找的位置是在左半边还是右半边。

然后我们循环这一操作(请不要在意这画得跟s一样的流程图)：

#include<bits/stdc++.h>
using namespace std;
int n,x;
int a[100005];
int main(){
    scanf("%d%d",&n,&x);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
    }
    int l=1,r=n,mid;       //l为左边界,r为右边界,mid为当前点
    while(l<r){            //区间长度大于1时继续二分
        mid=(l+r)>>1;      //获取中间点
        if(a[mid]>=x){     //判断:中间点小于等于x
            r=mid;         //答案处于左半段
        }
        else{
            l=mid+1;       //否则答案处于右半段
        }
    }
    printf("%d",l);       //此时l=r,即为答案
    return 0;
}

(然后你就A了一道非常水的题)

由于二分法非常非常常用，C++甚至有一个专门的函数(所以刚才的代码只是练练手)

这个伟大的函数即lower_bound它的格式是:lower_bound(a,a+n,x),其中a是数组名，n是数组长度，相信有基础的同学都知道这里的a是数组的开始地址，a+n是结束地址的下一个,x就是要查找的数，请注意，这个函数的返回值是一个地址，而如果你想知道下标，需要减去开始地址，也就是lower_bound(a,a+n,x)-a

通过这个函数就可以写出一个非常之短的代码：

#include<bits/stdc++.h>
using namespace std;
int n,x;
int a[100005];
int main(){
    scanf("%d%d",&n,&x);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
    }
    printf("%d",lower_bound(a,a+n,x)-a);
    return 0;
}

某著名OIer说过(别问我，我也不知道是谁)：

二分不是一种特定的算法，而是一种思想，这种思想在各种地方都有涉及，它使得时间复杂度上画上了一个精美的log

有了二分的思想，我们就可以来写一个可爱的线段树二分答案了。

二分答案，其实就是在不断缩小答案的区间，可以达到带log的复杂度，二分查找要求数组有序，二分答案则要求答案具有单调性，具体来说：若x>y且y对应的值为b，x对应的值为a，则一定有a>b

同时，我们注意到二分答案一般用来求最值问题，标志词：最大值最小，最小值最大

同时，还存在另外一种二分答案，即实数二分，它的思想与一般二分相同，但通常用来求解一个高次方程或者一些奇奇怪怪的带小数的问题