c - 在 C 中实现严格的下界

Question

我想出了这个解决方案来在排序数组中实现严格的下界:

long lowerBound(long key, long size, long *a){
    long low = 0, high = size, mid;
    if(a[low] >= key){
        return -1;
    }
    while(low < high){
        mid = (low+high)/2;
        if(a[mid] >= key){
            high = mid - 1;
        } else{
            low = mid;
        }
    }
    return low;
}

但这似乎不起作用。它在某些测试用例中失败。例如:

A[7] = {0, 1, 1, 3, 5, 5, 10}

键 = 4

进入无限循环。

这是测试运行:

第一次迭代后: 低= 3，高= 7，中= 3

第二次迭代后: 低= 3，高= 4，中= 5

第三次迭代后: 低= 3，高= 4，中= 3。 然后就卡住了。

任何人都可以指出我正确的方向吗？提前致谢!!

Answer 1

它会“卡住”，因为当你的 low等于 high - 1 , mid变成low :(low+low+1)/2 == low ，然后a[mid] >= key是 false和mid设置为low再次。您需要设置low至mid + 1如果a[mid] < key并设置high至mid否则。然后你会找到第一个出现的key，或者，如果没有元素等于key，则找到第一个大于key的元素，如果所有元素都小于key，你会得到初始值为高。

UPD:并且，由于它是二分搜索，因此您将总是得到 low == high - 1 。下次记住!

UPD2:还有一件事!最好使用mid = low+((high-low)/2) ，因为这可以防止一些溢出错误。