在 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

它得到 "stuck" 因为当你的 low 等于 high - 1, mid 变成 low: (low+low+1)/2 == low, 那么 a[mid] >= key 是 false 并且 mid 再次设置为 low。如果 a[mid] < key，则需要将 low 设置为 mid + 1，否则，请将 high 设置为 mid。然后你会发现第一次出现key或者如果没有元素等于key，第一次出现大于key的元素，如果所有元素都小于key，你会得到high.

的初始值

UPD: 而且，因为它是 二分查找， 你会总是得到 low == high - 1。下次记住！

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

Answer 2

举个例子：

low = 3
high = 4

那么你的代码会做什么？

while(low < high){         // True as 3 is less than 4
    mid = (low+high)/2;    // (3+4)/2 --> mid = 3
    if(a[mid] >= key){     // a[3] is 3. And 3 isn't greater or equal 4 so this is false
        high = mid - 1;
    } else{                // So you take the else part

        low = mid;         // low is assigned 3. So you are back
                           // where you started and have an endless loop
    }

您需要确保对 low 和 high 的赋值不仅仅是分配它们已有的值。

例如：

else {
    if (low == mid) return low;
    low = mid;
}

Answer 3

您从 high = size 开始，因此上限超出范围并且应该保持这种状态，也就是说，它永远不是解决方案。

因此出现两个错误：结束条件和新 high 值的设置。

结束条件应该是

while (high - low > 1)

之后的解决方案将是 low。并且新 high 值的设置应该是

if(a[mid] > key){               // change from >=
    high = mid;                 // mid is not valid
}

Answer 4

如果数组的每个元素都是唯一的，您可以使用以下内容：

long binsearch(long *a, long size, long key) {
    long lo = 0;
    long hi = size-1;

    if (hi == -1)
       return -1;

    while (1) {
       long mid = ( lo + hi ) / 2;
       if (a[mid] == key)
          return mid;

       if (a[mid] < key) {
          hi = mid - 1;
          if (lo > hi)
             return ~mid;
       } else {
          lo = mid + 1;
          if (lo > hi)
             return ~lo;
       }
    }
}

但是你的数组可能有重复项，而你想找到第一个，所以我们需要调整匹配项。

long binsearch_first(long *a, long size, long key) {
    long lo = 0;
    long hi = size-1;

    if (hi == -1)
       return -1;

    while (1) {
       long mid = ( lo + hi ) / 2;
       if (a[mid] == key && ( mid == 0 || a[mid-1] != key ))
          return mid;

       if (a[mid] <= key) {
          hi = mid - 1;
          if (lo > hi)
             return ~mid;
       } else {
          lo = mid + 1;
          if (lo > hi)
             return ~lo;
       }
    }
}

您可能已经注意到特殊的 return 值。它具有 returning 的优势，如果 key 不存在，它就会被发现。如果您想将 key 添加到数组中，这会告诉您要插入的位置。

long i = binsearch_first(a, a_size, key);
if (i >= 0) {
   printf("The first %ld was found at index %ld.\n", $key, i);
} else {
   printf("%ld wasn't found. It would have been found at index %ld.", $key, ~i);
}

在 C 中实现严格的下限

Implementing strictly lower bound in C

c

arrays

sorting

binary-search