代码

const int N=1e8;
const int cnt=50;
const int sz=N/cnt;

int binary_search(const unsigned *a, int n, unsigned x){
  static int vis, w[cnt+3];
  if (!vis){
    vis=1;
    for (int i=0;i<cnt;++i) w[i]=a[i*sz];
  }
  int l=0, r=cnt, mid;
  for (;l+1<r;){
    mid=l+r>>1;
    x<w[mid]? r=mid: l=mid;
  }
  for (l*=sz,r*=sz;l<r;){
    mid=l+r>>1;
    if (a[mid]==x) return mid;
    x<a[mid]? r=mid: l=mid+1;
  }
}

评测结果