为什么在这种二进制搜索排序数组的场景中仍然存在错误情况?

仅制造 1

while(左<右)

while(左<=右)

您的代码当前正在执行 . 你需要 包括你的案子。

例如。 使用以下测试用例尝试您的代码:

{ 1, 3, 5 }, 4) -> should output 2
{ 1, 3, 5 }, 2) -> should output 1
{ 1, 3, 5 }, 3) -> should output 1
{ 1, 3, 5 }, 6) -> should output 3
{ 1, 3, 5 }, 0) -> should output 0

其中大多数都是现有代码的失败。

我们的目标是找出 middle 小于 给定的数字和 middle + 1 它。当然,我们可以使用二进制搜索(修改)来实现这一点。

我修改了经典二进制搜索的代码以包含这些情况(以及代码中添加的注释):

while (left <= right) {
    middle = left + (right - left) / 2;
    if (sortedArray[middle] < lessThan && (middle + 1) < sortedArray.length
            && sortedArray[middle + 1] > lessThan) {
        // we have the point where middle is less and middle+1 is greater than given num
        return middle + 1;
    } else if (sortedArray[middle] == lessThan) {
        // we have found the number itself
        return middle;
    } else if (sortedArray[middle] < lessThan) {
        // recur in right part
        left = middle + 1;
    } else if (sortedArray[middle] > lessThan) {
        // recur in left part
        right = middle - 1;
    }
}

// given number is either lesser/bigger than all elements in the array
return lessThan < sortedArray[0] ? 0 : sortedArray.length;

How can I simplify this working Binary Search code in C?

这特别适合你的情况。由于您试图找到一个位置而不是一个元素,因此您可以简化代码并使其更快,方法是每次迭代仅进行一次比较,如下所示:

public static int countNumbers(int[] sortedArray, int lessThan) {
    int start = 0, limit = sortedArray.length;
    while(start < limit) {
        int test = start + ((limit-start)>>1);
        if (sortedArray[test] < lessThan) {
            start = test+1;
        } else {
            limit = test;
        }
    }
    return start;
}