search - 二分查找查找大于或等于给定键的元素

Question

我的代码片段是:

int bs_greaterthan_or_equal(int *a, int key, int low, int high) {
    while(low<high) {
    int mid = low +(high-low)/2.0;
    if(a[mid]<key) {
    low = mid + 1;
    }
    else high = mid;
    }

    return high;
}

但即使当我搜索大于数组中最后一个元素的数字时，它也会返回最后一个索引

例如 a[] = {1,3,10,15,20,25,27} 键 = 28 返回 7

Answer 1

But even when i search a number greater than last element in the array it returns the last index

因为这就是它的设计目的。从技术上讲，它返回最后一个索引 + 1。

注意条件:

if(a[mid]<key) {
low = mid + 1;
}

当查找大于(或等于)数组最后一个元素的元素时，上述条件将始终计算为 true。当到达最后一个元素本身时，循环终止，其中 low设置为比最后一个索引多 1。

当您在示例中搜索键 28 时，low被重复更新，因为上述条件总是评估为真。当mid等于 6，则 a[mid]仍然小于 28，所以 low设置为mid + 1 ，即7。此时，low和high变得相等(请注意 high 从未被修改)并且循环终止。该函数返回 7。

如果您希望在搜索大于或等于数组中最后一个元素的数字时返回特定内容(例如 -1)，您可以按如下方式修改代码。

int bs_greaterthan_or_equal(int *a, int key, int low, int high) {
    int max_limit = high;
    while(low<high) {
    int mid = low +(high-low)/2.0;
    if(a[mid]<key) {
    low = mid + 1;
    }
    else high = mid;
    }

    return high == max_limit ? -1 : high;
}

如果数组包含给定键更大或相等的元素，high将存储其索引。否则，最后，high将保持等于 max_limit ，这意味着搜索过程找不到这样的元素，因此将返回 -1。