二分查找求下界时的bug - c++编程基础

二分查找求下界时有个小小的bug。。。

假如我们想在有序的数列中找到小于等于num的第一个数，如果这个数存在，那么我们很容易就可以通过二分求下界的方法找到，如果不存在，那么二分返回的值就有问题了。。请看测试代码：

#include  
int a[10], n = 10;//用数组a存0~20的奇数  
int lower_bound(int num)  
{  
    int low = 0, high = n;  
    while(low < high)  
    {  
        int mid = low + (high - low)/2;  
        if(a[mid] >= num) high = mid;  
        else low = mid + 1;  
    }  
    return low;//返回的是位置  
}  
int main()  
{  
    int i,j;  
    for(i = 0,j = 1; i < n; i ++, j += 2)  
    a[i] = j;  
    for(i = 0; i < 10; i ++)  
    printf("a[%d]：%d\n",i,a[i]);  
  
    for(i = 2; i < 10; i += 1)  
    {  
        int x = lower_bound(i);  
        printf("查找的数：%d 返回的位置：%d 该位置的数：%d\n",i,x,a[x]);  
    }  
    return 0 ;  
}

这是结果：

通过测试发现，当我们要查找的数num不在数列中时，那么二分返回的位置的数刚好大于num