转载

细说“二分查找”

前言：

二分算法很常见，也很简单。但确实很高效！有了它，我们常常可以避免"暴力"！

-------------------------------------------------

1.二分漏洞

先贴一段代码，大家看看有没有问题？

 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 }

分析：

当你拿上述的代码进行测试的时候，一切正常，看似风平浪静...那么，问题在哪儿呢~

第2行---->当数组长度为“1”的时候，无论查找什么数直接返回“-1”；
第3行---->一般人这么写没什么影响，但注意到边界值的话，想想还是可能出现"l+r"溢出的;

----------------------------------------

2.改进版的二分查找

 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 }

测试结果：

细说“二分查找”

----------------------------------------

3.“二分查找“key的最小（最大）下标

 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 }

上述代码的实现过程如下图：

细说“二分查找”

---------------------------------------------------

测试结果：

细说“二分查找”

4.不仅仅只是查找：快速统计有序数列中key的个数

分析：

在有序数组中，本来我们大可通过一次遍历对”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 }