0

我正在尝试稍微更改二进制搜索，因此我想找到最小索引，以便 Array[index] >= key. 因此，如果我有一个类似的数组int A[5] = {1,5,10,15,20}并且我调用search(A, 12, 5)（其中 5 只是数组的长度），它将返回=> 3since A[3] = 15 >= 12。如果我搜索超过 20 的东西，它只会给我5返回或其他任意数字。

我正在尝试将它写得尽可能接近传统的二进制搜索。有什么帮助吗？

（这里是传统的二分查找）

int binarysearch(int A[], int key, int length) {
    int low = 0;
    int high = length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (key < A[mid]) {
            high = mid - 1;
        } else if (key > A[mid]) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}
4

2 回答 2

0

我认为最好的方法是在密钥小于中间条目时添加一个检查，该中间条目将查看前一个条目。如果键大于该条目，我们就有答案（因为如果您从列表中降级，则该条目不会大于该键）。所以，代码看起来像这样：

int low = 0;
int high = length - 1;
while (low <= high)
{
    int mid = (low + high) / 2;
    if (key < A[mid])
    {
        high = mid - 1;
        if (high < 0 || key > A[high])
        {
            return mid
        }    
    }
    else if (key > A[mid])
    {
        low = mid + 1;
    }
    else
    {
    return mid;
    }
}
return -1;

如果您的列表允许重复，它需要更复杂，但它应该可以工作。

于 2013-03-08T00:59:08.000 回答
-1

而不是return -1，只是返回mid

于 2013-03-08T01:01:50.870 回答