第一章的目录
二分是为了解决快速查询问题与最小的最大值或最大的最小值等问题而建立的。
看一道例题，acwing中无。
有一个上升数组$a$,$q$组询问。
每组询问查询数$x$在$a$中出现的位置。
数据保证$a$不重复，且每一组询问都有答案。
这道题目很简单，扫一遍就好了，复杂度$O(q*len(a))$
但是：
$1\le q \le 10^5$
$1\le len(a) \le 10^6$
啊啊啊啊……

超时……

注意，$a$是上升数组，所以……

重点来临

如果有一个数$a<b$,且$c<a$,则$c<b$

那么如果$a_i<x$,那么

• $a_1<x$
• $a_2<x$
• $a_3<x$
• $a_{i-2}<x$
• $a_{i-1}<x$

所以只要最中间进行一次比较，那么就可以排除一半的数
这样的时间复杂度就是$O(qlog(len(a)))$
能过！

二分有两种模板：

版本1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

C++代码模板（相当于lower_bound）：

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

C++代码模板（相当于upper_bound）：

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

这是整数二分。

先来看几道整数二分的题目

AcWing 789. 数的范围

两个模板结合一下
pong……

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q,l,r,mid;
int a[N];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    while(q--)
    {
        int x;
        scanf("%d",&x);
        l=0,r=n-1;
        while(l<r)
        {
            mid=(l+r)/2;
            if(a[mid]>=x) r=mid;
            else l=mid+1;
        }
        if(a[l]!=x)
        {
            printf("-1 -1\n");
            continue;
        }
        cout<<l<<' ';
        l=0,r=n-1;
        while(l<r)
        {
            mid=(l+r+1)/2;
            if(a[mid]<=x) l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
}

接下来讲浮点二分
浮点二分直接分就好了

看例题!

AcWing 790. 数的三次方根

直接做

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include<iomanip>
using namespace std;
long double n;
int main()
{
    cin>>n;
    long double l,r;
    if(n>0) l=0,r=100;
    else if(n==0) printf("%.6lf",0.00);
    else l=-100,r=0;
    for(int i=1;i<=100;i++)//这里我懒得算精度了，直接分100次，理论精度$2^(-100)$
    {
        long double mid=(l+r)/2;
        if(mid*mid*mid>=n) r=mid;
        else l=mid;
    }
    cout<<fixed<<setprecision(6)<<l;
}

点个赞再走也行啊……