在某本书上学到了用倍增写的二分查找：

//主要部分
//这段代码是用来在A[1..n]中查询x的。
int p=0,k=1; 
while(k) if(p+k<=n&&A[p+k]<x)
p+=k,k<<=1; else k>>=1;
ans=(A[p+1]==x?p+1:-1);

然后在犇犇，有位神犇抨击了倍增算法……
（大致意思是，倍增常数大，二分常数更小）

然后心血来潮，优化了倍增：

//主要代码。功能同上
int k=1<<20; while(k){
    if(p|k<=n&&A[p|k]<x) p|=x;
    k>>=1;
}

在$n$恰好是$2$的次幂时，可以直接使$k=\frac{n}{2}$，这样就不需要越界检查，优化代码。

然后进行了一些测试：

//数据生成器
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
using namespace std;
const int MAXN =1e9,MAXM=(1<<20)+3;
int n=1<<20,m=1e7,P[MAXM];
mt19937 MT(23333);
int main(){
    freopen("in.txt","w",stdout),printf("%d %d\n",n,m);
    up(1,n,i) P[i]=MT()%MAXN+1; sort(P+1,P+1+n);
    up(1,n,i) printf("%d ",P[i]); puts("");
    up(1,m,i) printf("%d ",P[MT()%n+1]);
    return 0;
}

这个生成器会生成长度为$2^{20}$的数组，以及长度为$10^7$的询问。

//倍增优化
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
using namespace std;

typedef long long LL;
const int INF =2147483647;
int qread(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0')
    w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9')
    ret=ret*10+c-'0';
    return ret*w;
}
const int MAXN =(1<<20)+3,MAXM=1e7+3;
int A[MAXN],B[MAXM];
int n,m,p,w;
int main(){
    freopen("in.txt","r",stdin);
    freopen("out1.txt","w",stdout);
    n=qread(),m=qread();
    up(0,n-1,i) A[i]=qread();
    up(0,m-1,i) B[i]=qread();
    int a=clock();
    up(0,m-1,i){
        if(A[0]==B[i]) {/*printf("%d ",1);*/continue;}
        w=n,p=0; while(w>>=1) if(A[p|w]<B[i]) p|=w;
//      printf("%d ",A[p+1]==B[i]?p+2:-1);
    }
    int b=clock(); freopen("CON","w",stdout);
    printf("You used [%dms].\n",b-a);
    return 0;
}

就是将上面的代码实现后的结果。

//STL(无O2)的二分查找(lower_bound)
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
using namespace std;

typedef long long LL;
const int INF =2147483647;
int qread(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0')
    w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9')
    ret=ret*10+c-'0';
    return ret*w;
}
const int MAXN =(1<<20)+3,MAXM=1e7+3;
int A[MAXN],B[MAXM];
int n,m,p,w;
int main(){
    freopen("in.txt","r",stdin);
    freopen("out2.txt","w",stdout);
    n=qread(),m=qread();
    up(0,n-1,i) A[i]=qread();
    up(0,m-1,i) B[i]=qread();
    int a=clock();
    up(0,m-1,i){
        p=lower_bound(A,A+n,B[i])-A;
//      printf("%d ",A[p]==B[i]?p+1:-1);
    }
    int b=clock(); freopen("CON","w",stdout);
    printf("You used [%dms].\n",b-a);
    return 0;
}

非常经典的$\rm STL$用法。

//手写二分。
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
using namespace std;

typedef long long LL;
const int INF =2147483647;
int qread(){
    int w=1,c,ret;
    while((c=getchar())> '9'||c< '0')
    w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9')
    ret=ret*10+c-'0';
    return ret*w;
}
const int MAXN =(1<<20)+3,MAXM=1e7+3;
int A[MAXN],B[MAXM];
int n,m,p,w,l,r,mid;
int main(){
    freopen("in.txt","r",stdin);
    freopen("out3.txt","w",stdout);
    n=qread(),m=qread();
    up(0,n-1,i) A[i]=qread();
    up(0,m-1,i) B[i]=qread();
    int a=clock();
    up(0,m-1,i){
        l=0,r=n-1;
        while(l<r){
            mid=(l+r)>>1;
            A[mid]>=B[i]?(r=mid):(l=mid+1);
        }
//      printf("%d ",A[l]==B[i]?l+1:-1); 
    }
    int b=clock(); freopen("CON","w",stdout);
    printf("You used [%dms].\n",b-a);
    return 0;
}

（已经用程序比对过了每个程序的输出，都相等，因此注释掉了输出）。

然后测试结果是：

• 倍增优化$7s$左右。

• $\verb!lower_bound!$（无$\rm O2$）为$14.5s$左右。

• 手写二分是$9s$左右。

---

当$n$不是二的次幂的时候，倍增那边要进行一些处理（比如说，将$n$补成二的次幂，后面的部分都用极大值填充），会增长一些常数（但不是很大）。

所以，既然倍增要略优于二分，且更容易调试，那么为什么倍增并没有被像二分那样地普及呢？

还是说我自带大常数，导致二分常数过大