调试二分查找代码

Question

我遇到了这个面试问题。它说我们必须对排序数组进行二分搜索。以下是相关代码。该代码存在错误，因此无法给出正确的答案。您必须更改代码才能给出正确的输出。

条件：不允许添加行，并且只能更改代码中的三行。

int solution(int[] A, int X) {
    int N = A.length;
    if (N == 0) {
        return -1;
    }
    int l = 0;
    int r = N;
    while (l < r) {
        int m = (l + r) / 2;
        if (A[m] > X) {
            r = m - 1;
        } else {
            l = m+1;
        }
    }
    if (A[r] == X) {
        return r;
    }
    return -1;
}

我自己尝试了很多，但缺少一些测试用例。

Answer 1

我讨厌这个问题，这是那些“不必要的约束”问题之一。正如其他人所提到的，问题在于，如果找到该值，则不会返回该值。由于愚蠢的说明说您无法添加任何代码，因此您可以像这样破解它：

if (A[m] >= X) {
    r = m;
} else {
    l = m;
}

这会降低性能，但它应该可以工作。

Answer 2

需要在循环内检查搜索到的值，如果找到则退出

示例代码：

int solution(int[] A, int X) {
    int N = A.length;
    if (N == 0) {
        return -1;
    }
    int l = 0;
    int r = N;
    while (l <= r) { // change here, need to check for the element if l == r
                     // this is the principal problem of your code
        int m = (l + r) / 2;
        if (A[m] == X) { // new code, for every loop check if the middle element
            return r;    // is the search element for early exit.
        } else if (A[m] > X) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return -1;
}

另一个问题是，当元素位于数组中时，您正在测试更多所需的元素。

Answer 3

试试这个：

int l = 0;
int r = N - 1; // changed
while (l <= r) { // changed

Answer 4

您必须了解所使用的方法。您正在寻找第一个 >= X 的元素。

你想要 k 和 i < k <=> A[i] < X.

L 代表左。它是 k 的下限。你有我 < l => A[i] < X.

R 代表右。它是 k 的上限。你有 i >= r => A[i] >= X.

您的目标是缩小范围并让 l = r。为此，您需要检查中间的值，即 m = (r+l)/2。
如果 A[m] >= X，则 m 满足 r 的条件。您可以设置 r = m。
如果 A[m] < X then A[m] belongs to the part left of l. So you can set l to the right of m, l = m+1.

每次循环都会缩小 l 和 r 之间的范围。当你到达l==r时，你就找到了我称之为k的点。 A[k] 是 >= X 的最小数。您只需检查它是否 == X 或 > X。

从那里你应该能够修复代码。

PS：请注意，k（又名 l 或 r）可以 >= A.length。您需要验证一下。

Answer 5

变化 1 -

while(l < r-1)

2-

r = m;

3-

l= m;

完整代码

static int solution(int[] A, int X) {
int N = A.length;
if (N == 0) {
    return -1;
}
int l = 0;
int r = N ; 
while (l < r - 1 ) { //Here
    int m = (l + r) / 2;
    if (A[m] > X) {
        r = m; //Here
    } else {
        l = m ; //Here
    }
}
if (A[l] == X) { 
    return l;  
}
return -1;

}