java - 我的基本二进制搜索方法不适用于 Java 中 int 数组中的一个特定值

Question

我是一名 Java 初学者，这里有一个小程序可以输出 int 数组中搜索到的 int 值的索引。这是代码

public static void main(String[] args) {

    int rank =findNumber(7, new int[]{2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79});
    System.out.println("Your number's index is " + rank);

}

public static int findNumber(int key, int... numbers) {
    int low = 0;
    int high = numbers.length - 1;
    int mid = (low + high) / 2;
    int rank = 0;
    for (int i = low; i < high; i++) {
        if (key < numbers[mid]) {
            high = mid;
            mid = (low + high) / 2;
        } else if (key > numbers[mid]) {
            low = mid;
            mid = (low + high) / 2;
        } else {
            rank = mid;
            return rank;
        }
    }
    return rank;
}

问题是它适用于数组中的所有数字，除了 7。我试图通过调试找到它，但一无所获。

谁能告诉我这是什么问题？

Answer 1

问题是，即使您正在更改 low和 high ，循环取决于变量 i它仅通过在循环的每次迭代结束时递增而改变。但是，二分查找的终止条件应该是low >= high。 .你现在的循环条件，i < high与low之间的关系无关和 high ，这可能会导致循环过早结束或在二进制搜索已经结束时继续进行。

我建议做的是初始化 low在 for 循环中，将终止条件更改为 low <= high ，并制定更新序列 mid = (low + high)/2因为除非你找到数字，否则你在 for 循环的每次迭代之后都会这样做。然而，此时循环将终止返回找到的数字的索引。这是它的样子，

public static int findNumber(int key, int... numbers) {
    int high = numbers.length - 1;
    int mid = (0 + high) / 2; //replaced low with 0 here
    int rank = 0;
    for (int low = 0; low <= high; mid = (low + high) / 2) {
        if (key < numbers[mid]) {
            high = mid - 1;
        } else if (key > numbers[mid]) {
            low = mid + 1;
        } else {
            rank = mid;
            return rank;
        }
    }
    return rank;
}

编辑:所以在一些测试之后，我意识到另一个错误是你如何更新 low和 high在你的方法中。之前更新这些变量时，您只是在做 high = mid和 low = mid但这是有风险的，因为通过这样做，你基本上仍然保持 numbers[mid]在将在循环的下一次迭代中评估的范围内。这个号码，numbers[mid]应该从范围中省略，因为键要么小于、大于或等于 numbers[mid] .如果 key 小于或大于 numbers[mid] ，那么就没有必要让它继续前进到下一个要通过二进制搜索查看的数字范围。所以一个解决方案是通过 low = mid + 1 更新低和高和 high = mid - 1 .