前言:
二分算法很常见,也很简单。但确实很高效!有了它,我们常常可以避免"暴力"!
-------------------------------------------------
先贴一段代码,大家看看有没有问题?
1 int binarySearch(int *arr,int l,int r,int key){
2 while(l<r){
3 int m=(l+r)/2;
4 if(arr[m]==key){
5 return m;
6 }else if(arr[m]>key){
7 r = m-1;
8 }else {
9 l = m+1;
10 }
11 }
12 return -1;
13 }
分析:
当你拿上述的代码进行测试的时候,一切正常,看似风平浪静...那么,问题在哪儿呢~
----------------------------------------
1 #include<cstdio>
2 #define N 5
3
4 /*'l'起始下标,'r'结束下标*/
5 int binarySearch(int *arr,int l,int r,int key){
6 while(l<=r){
7 int m=l+(r-l)/2;
8 if(arr[m]==key){
9 return m;
10 }else if(arr[m]>key){
11 r = m-1;
12 }else {
13 l = m+1;
14 }
15 }
16 return -1;
17 }
18 int main(){
19 int arr[N]={1,3,3,5,11};
20 printf("%d\n",binarySearch(arr,0,N,1));
21 printf("%d\n",binarySearch(arr,0,N,3));
22 printf("%d\n",binarySearch(arr,0,N,100));
23 return 0;
24 }
测试结果:
----------------------------------------
1 #include<cstdio>
2 #define N 5
3
4 int binarySearch(int *arr,int l,int r,int key){
5 while(l<=r){
6 int m=l+(r-l)/2;
7 if(arr[m]==key){
8 return m;
9 }else if(arr[m]>key){
10 r = m-1;
11 }else {
12 l = m+1;
13 }
14 }
15 return -1;
16 }
17 //已知存在一或多个‘key’,求key的最小下标
18 int lowerBound(int *arr,int l,int r,int key){
19 while(l<r){
20 int m=l+(r-l)/2;
21 if(arr[m]==key){
22 r=m; //为了得到更小的下标,赋值给上边界,向下逼近
23 }else if(arr[m]>key){
24 r=m-1;
25 }else{
26 l=m+1;
27 }
28 }
29 return l;
30 }
31
32 int upperBound(int *arr,int l,int r,int key){
33 //注意:补充一个特殊位
34 r = r+1;
35 while(l<r){
36 int m=l+(r-l)/2;
37 //printf("l:%d,r:%d,m:%d\n",l,r,m);
38 if(arr[m]==key){
39 l=m+1; //返回key最大下标+1(?思考为什么无法直接返回key的最大下标)
40 }else if(arr[m]>key){
41 r=m-1;
42 }else{
43 l=m+1;
44 }
45 }
46 return l;
47 }
48 int main(){
49 int arr[N]={1,3,3,5,11};
50 printf("--------lower--------\n");
51 printf("%d\n",lowerBound(arr,0,N-1,1));
52 printf("%d\n",lowerBound(arr,0,N-1,3));
53 printf("%d\n",lowerBound(arr,0,N-1,11));
54 printf("%d\n",lowerBound(arr,0,N-1,0));
55 printf("--------upper--------\n");
56 printf("%d\n",upperBound(arr,0,N-1,1));
57 printf("%d\n",upperBound(arr,0,N-1,3));
58 printf("%d\n",upperBound(arr,0,N-1,11));
59 printf("%d\n",upperBound(arr,0,N-1,100));
60 return 0;
61 }
上述代码的实现过程如下图:
---------------------------------------------------
测试结果:
分析:
在有序数组中,本来我们大可通过一次遍历对”key“进行计数,时间复杂度:O(n);但有了二分查找!我们下面还是考虑如何提高效率吧~
首先,我们都知道在一个有序数列中,假如同时存在多个”key“,那么用我们上面binarySearch()函数返回的是数列中其中一个key的下标(具有随机性,跟key在数列的位置有关!)
怎么求解呢?其实,我们上面的例子就是为这一小节的内容准备的。但是我们需要考虑2种情况,一种是要查找的key本来就不存在数列中,第二种是key存在数列中。保险一点的做法是,我们先用普通的二分查找判断一下是否存在,若存在再使用上一小节的lowerBound()和upperBound()方法。但,巧妙的是不管key在不在我们都可以使用上一小节的方法。因为我们要计算的是差值,不是具体的下标!所以,
方法一:利用lowerBound()和upperBound()算出数列中key的最大和最小坐标i,j之后,进行相减;
方法二:只需要lowerBound()方法。这里应用了一点小技巧,即:要查找数列中有多少个”key“,那么我利用lowerBound()函数分别得到"key"和”(key+1)“的起始坐标值(不管”key+1“实际存不存在),两者相减即是答案!
1 #include<cstdio>
2 #define N 5
3
4 int binarySearch(int *arr,int l,int r,int key){
5 while(l<=r){
6 int m=l+(r-l)/2;
7 if(arr[m]==key){
8 return m;
9 }else if(arr[m]>key){
10 r = m-1;
11 }else {
12 l = m+1;
13 }
14 }
15 return -1;
16 }
17 //已知存在一或多个‘key’,求key的最小下标
18 int lowerBound(int *arr,int l,int r,int key){
19 while(l<r){
20 int m=l+(r-l)/2;
21 if(arr[m]==key){
22 r=m; //为了得到更小的下标,赋值给上边界,向下逼近
23 }else if(arr[m]>key){
24 r=m-1;
25 }else{
26 l=m+1;
27 }
28 }
29 return l;
30 }
31
32 int upperBound(int *arr,int l,int r,int key){
33 //注意:补充一个特殊位
34 r = r+1;
35 while(l<r){
36 int m=l+(r-l)/2;
37 //printf("l:%d,r:%d,m:%d\n",l,r,m);
38 if(arr[m]==key){
39 l=m+1; //返回key最大下标+1(?思考为什么无法直接返回key的最大下标)
40 }else if(arr[m]>key){
41 r=m-1;
42 }else{
43 l=m+1;
44 }
45 }
46 return l;
47 }
48 int countX(int *a,int l,int r,int key){
49 return upperBound(a,l,r,key)-lowerBound(a,l,r,key);
50 }
51 int main(){
52 int arr[N]={1,3,3,5,11};
53 printf("需要统计个数的X存在于数组中:\n");
54 printf("方式一输出:%d\n",countX(arr,0,N-1,3));
55 printf("方式二输出:%d\n",lowerBound(arr,0,N-1,3+1)-lowerBound(arr,0,N-1,3));
56
57 printf("需要统计个数的X不存在于数组中:\n");
58 printf("方式一输出:%d\n",countX(arr,0,N-1,2));
59 printf("方式二输出:%d\n",lowerBound(arr,0,N-1,2+1)-lowerBound(arr,0,N-1,2));
60
61 return 0;
62 }
测试结果:
-----------------------------
注意: