二分查找

比如我今天想写一个二分查找：

首先，很容易的写下 int bSearch(int begin, int end, int e)

然后，很自然的定义 int mid, left = begin, right = end;

接下来怎么写呢？while(left < right)？while(left <= right)？while(mid == left)？while(mid == right)？………………真正一个写程序人会想纠结好一会儿，我们就选一个吧while(left < right)

下面，也很自然，mid = (left + right) >> 1; 用位运算能节省一些时间呢！

现在呢？又是纠结的时候了吧？if(num[mid] > e)？if(num[mid] >= e)？我们也随便选一个吧，if(num[mid] > e)

其实，下面你会不断纠结……right = mid;这是正常人的写法，但是有时候也会看到别人写成right = mid - 1;我们也考虑下吧，但是现在我们就直接写right = mid;

有if了当然也会有else，然后理所当然 left = mid;同样记住还有一个选择left = mid + 1;

不错，整个while循环搞定了，最后就是返回了，写下return的时候是不是又纠结了？left？right？mid？算了，就写mid吧，整个程序就写好了，如下：

 1 int bSearch(int begin, int end, int e)  2 {  3     int mid, left = begin, right = end;  4     while(left < right)  5     {  6         mid = (left + right) >> 1;  7         if(num[mid] > e) right = mid;  8         else left = mid;  9     } 10     return mid; 11 }

呵呵呵呵呵。。。。。。。。。。。。。。

--------------------------------------我是吐槽和正解的分割线----------------------------------------------

其实吧二分查找这个东西我们真的忽略太多了。。。也只有当我写主席树的时候貌似才真正注意到不同给跪。。。

我简单结合一下STL中的lower_bound()谈谈理解：

 1 #include<iostream>  2 #include<cstdio>  3 #include<cmath>  4 #include<algorithm>  5 #include<queue>  6 #include<cstring>  7 #define PAU putchar(' ')  8 #define ENT putchar('/n')  9 using namespace std; 10 int A[100]; 11 int find1(float v){ 12     int L=0,R=7,M; 13     while(L<=R){ 14         M=L+R>>1;if(A[M]<v) L=M+1;else R=M-1; 15     } return L; 16 } 17 int find2(float v){ 18     int L=0,R=7,M; 19     while(L<R){ 20         M=L+R>>1;if(A[M]<v) L=M+1;else R=M; 21     } return L; 22 } 23 int find3(float v){ 24     int L=0,R=7,M; 25     while(L<=R){ 26         M=L+R>>1;if(A[M]<v) L=M+1;else R=M-1; 27     } return R+1; 28 } 29 int find4(float v){ 30     int L=0,R=7,M; 31     while(L<R){ 32         M=L+R>>1;if(A[M]<v) L=M+1;else R=M; 33     } return R; 34 } 35 int find5(float v){ 36     int L=0,R=7,M; 37     while(L<=R){ 38         M=L+R>>1;if(A[M]>v) R=M-1;else L=M+1; 39     } return L; 40 } 41 int find6(float v){ 42     int L=0,R=7,M; 43     while(L<R){ 44         M=L+R>>1;if(A[M]>v) R=M;else L=M+1; 45     } return L; 46 } 47 int find7(float v){ 48     int L=0,R=7,M; 49     while(L<=R){ 50         M=L+R>>1;if(A[M]>v) R=M-1;else L=M+1; 51     } return R+1; 52 } 53 int find8(float v){ 54     int L=0,R=7,M; 55     while(L<=R){ 56         M=L+R>>1;if(A[M]>v) R=M-1;else L=M+1; 57     } return R+1; 58 } 59 inline int read(){ 60     int x=0,sig=1;char ch=getchar(); 61     while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();} 62     while(isdigit(ch))x=10*x+ch-'0',ch=getchar(); 63     return x*=sig; 64 } 65 inline void write(int x){ 66     if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x; 67     int len=0,buf[15];while(x)buf[len++]=x%10,x/=10; 68     for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return; 69 } 70 void init(){ 71     A[0]=5; 72     A[1]=5; 73     A[2]=6; 74     A[3]=6; 75     A[4]=6; 76     A[5]=9; 77     A[6]=9; 78     A[7]=10; 79     float cv=6; 80     write(find1(cv));ENT; 81     write(find2(cv));ENT; 82     write(find3(cv));ENT; 83     write(find4(cv));ENT; 84     write(lower_bound(A,A+8,cv)-A);ENT; 85     write(find5(cv));ENT; 86     write(find6(cv));ENT; 87     write(find7(cv));ENT; 88     write(find8(cv));ENT; 89     write(upper_bound(A,A+8,cv)-A);ENT; 90     return; 91 } 92 void work(){ 93     return; 94 } 95 void print(){ 96     return; 97 } 98 int main(){init();work();print();return 0;}

这是我写的十个简单的查找的函数。

事实证明，这十个查找函数竟然全都是正确的，其中前五个返回了第一个重复的值，后五个返回了最后一个重复的值的地址+1。

至于速度，find1,2,5,6最快，STL最慢。

取左还是右，在于if()后面跟的是什么操作。

事实上，二分查找的变形还有许许多多。So，真正二分还是很神奇的，OI建议使用find1，移动光标速度会很快。（雾）

最后把主席树扔上来。。。

 1 #include<iostream>  2 #include<cstdio>  3 #include<cmath>  4 #include<algorithm>  5 using namespace std;  6 const int maxn=100000+10,maxnode=2000000+10;  7 int ls[maxnode],rs[maxnode],s[maxnode],root[maxn],A[maxn],num[maxn],ms,n,Q;  8 int find(int v){  9     int L=1,R=n,M; 10     while(L<=R){ 11         M=L+R>>1;if(num[M]<v) L=M+1;else R=M-1; 12     } return L; 13 } 14 void build(int x,int& y,int L,int R,int pos){ 15     s[y=++ms]=s[x]+1;if(L==R)return; 16     ls[y]=ls[x];rs[y]=rs[x];int M=L+R>>1; 17     if(pos<=M) build(ls[x],ls[y],L,M,pos); 18     else build(rs[x],rs[y],M+1,R,pos); return; 19 } 20 int query(int x,int y,int L,int R,int k){ 21     if(L==R) return L; 22     int M=L+R>>1,kth=s[ls[y]]-s[ls[x]]; 23     if(k<=kth) return query(ls[x],ls[y],L,M,k); 24     else return query(rs[x],rs[y],M+1,R,k-kth); 25 } 26 inline int read(){ 27     int x=0,sig=1;char ch=getchar(); 28     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();} 29     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar(); 30     return x*=sig; 31 } 32 inline void write(int x){ 33     if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x; 34     int len=0,buf[15];while(x) buf[len++]=x%10,x/=10; 35     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return; 36 } 37 void init(){ 38     n=read();Q=read();for(int i=1;i<=n;i++) num[i]=A[i]=read(); 39     sort(num+1,num+1+n);for(int i=1;i<=n;i++) build(root[i-1],root[i],1,n,find(A[i])); 40     return; 41 } 42 void work(){ 43     int a,b,c; 44     while(Q--){ 45         a=read();b=read();c=read(); 46         write(num[query(root[a-1],root[b],1,n,c)]); 47         putchar('/n'); 48     } 49     return; 50 } 51 void print(){ 52     return; 53 } 54 int main(){ 55     init();work();print();return 0; 56 }