java - 无法找到所需的索引

Question

这是一道面试题，让我修改代码-->

给定一个排序数组，如果元素存在，我必须找到该元素的数组索引，否则我必须返回 -1。以下是我的代码:

public static int returnIndex(int[] a, int x) {
    int n = a.length;
    if (n == 0) {
        return -1;
    }
    int l = 0;
    int r = n - 1;
    while (l < r) {
        int m = (l + r) / 2;
        if (a[m] > x) {
            r = m - 1;
        } else {
            l = m;
        }
    }
    if (a[l] == x) {
        return l;
    }
    return -1;
}

如果我必须找到中间元素，代码工作正常，但当我必须找到任何其他元素时代码失败(进入无限循环)。谁能指出错误？

我只能在此代码中进行 3 次修改。最坏情况时间复杂度-O(log(n))最坏情况空间复杂度-O(1)

Answer 1

你在这里尝试二分查找。所以你需要具备3个条件。 midValue > key，midValue < key 和 midValue == key。您只处理 2 个。此外，当 midValue > key 时，您需要将一个添加到索引中。所以像这样修改你的方法

public static int returnIndex(int[] a, int x) {
    int n = a.length;
    if (n == 0) {
        return -1;
    }
    int l = 0;
    int r = n - 1;
    while (l < r) {
        int m = (l + r) / 2;

        if (a[m] > x) {
            r = m - 1;
        } else if(a[m] < x){
            l = m + 1;
        } else {
            return m;
        }
    }
    return -1;
}

如果您这样做不是为了练习，您可以通过 Arrays.binarySearch() 方法实现同样的效果。