二分搜索

二分搜索技术很经典；讨论一下二分搜索的3种形式。

查值
查上界
查下界

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 //左闭右开
 6 int bsearch(int* A,int x,int y,int v) {
 7     int m;
 8     while(x<y) {
 9         m = x + (y-x)/2;
10         if(A[m]==v) return m;
11         else if(A[m]>v) y=m;
12         else x = m+1;
13     }
14     return -1;
15 }
16 
17 
18 int lowerbound(int* A,int x,int y,int v) {
19     int m;
20     while(x<y) {
21         m = x + (y-x)/2;
22         if(A[m]>=v) y=m;
23         else x = m+1;
24     }
25     return x;
26 }
27 
28 int upperbound(int* A,int x,int y,int v) {
29     int m;
30     while(x<y) {
31         m = x + (y-x)/2;
32         if(A[m]<=v) x=m+1;
33         else y=m;
34     }
35     return x;
36 }
37 
38 
39 int main()
40 {
41     int a[10] = {0,1,2,3,4,5,6,7,8,9};
42     printf("%d
",bsearch(a,0,10,9));
43 
44     int b[10] = {0,1,1,1,4,5,6,7,8,9};
45     printf("%d
",lowerbound(b,0,10,1));
46     printf("%d
",lowerbound(b,0,10,10));
47 
48     printf("%d
",upperbound(b,0,10,1));
49     printf("%d
",upperbound(b,0,10,10));
50 
51     return 0;
52 }

这里都是左闭右开的结构。

查值很好说，查不到返回-1；

查上界：

当中点值>v时，[x,y);中点值==v时，而左边可能还有，区间[x,y)，当中点<v时[m+1,y)

查下界：

当中点值>v时，[x,y)；中点值==v时，而右边可能还有[m+1,y)，当中点<v时[x,m)

这样的划分区间就是[L,R)，因为无论是查上界，还是下界的时候都可能查不到，这是返回值，就将是[x,y)的y，之前是一个左闭右开的区间。