Java 中的二进制搜索不会终止

Question

我一直在尝试在Java中实现binary search，程序在达到10后不会递增left。我可以很容易地在互联网上获得相同的代码，但我想弄清楚为什么我的代码不起作用。

class Test {
  public static void main(String[] args) {
    int[] li = { 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
        30 };
    int target = 19;
    int left = 0, right = li.length;
    while (left < right) {
      int mid = (right - left) / 2;
      if (li[mid] == target) {
        System.out.println(mid);
        break;
      }
      else if (li[mid] < target) {
        System.out.println("li[mid] < target");
        left = mid + 1;
        System.out.println(left);
      }

      if (li[mid] > target) {
        System.out.println("li[mid] > target");
        right = mid - 1;
      }
    }
  }
}

输出

li[mid] < target
10
li[mid] < target
10
li[mid] < target
10
li[mid] < target
10
li[mid] < target
10

Answer 1

多个重大错误。

你的根本问题是你没有调试你的代码；你不能运行 SO 或其他人每次你的代码不能立即工作 - 相信我，代码（由任何人编写，甚至是冬天的退伍军人）有太多的错误使它成为一个可行的计划:)

不只是打印 left。打印更多的东西，直到你很好地理解代码的实际作用。或者，更好的是，使用调试器并单步执行。首先在脑海中弄清楚应该发生什么，然后检查它是否真的发生了。

如果您这样做了，您会立即意识到 (right - left) / 2 不会计算平均值。你想要 (right + left) /2.

Answer 2

您的代码只需修改几处即可运行：

int left = 0, right = li.length - 1;

记住数组使用零基索引，所以最右边的索引是长度减一。

while (left < right)

二分查找最终会到达左 == 右的一个元素范围。

int mid = (right - left) / 2;

您需要将左索引添加到此结果以说明非零左索引。您的代码结果如下：
左 = 0，右 = 10 -> 中 = 5
左 = 5，右 = 10 -> 中 = 2 ** 应该是 7 **

您还应该如下所示清理分支语句。

int left = 0, right = li.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (target < li[mid]) {
        System.out.println("target < li[mid]");
        right = mid - 1;
        System.out.println(right);
    }
    else if (target > li[mid]) {
        System.out.println("target < li[mid]");
        left = mid + 1;
        System.out.println(left);
    }
    else {
        System.out.println(mid);
        break;
    }
}

我建议您在调试器中逐步执行此算法，以了解它失败的原因以及（一旦修复）它是如何工作的。

Answer 3

您对二分查找的概念理解正确，但还有一些小问题。首先，right 应设置为 li.length-1。然后，当您分配 mid 时，您还需要添加 left。代码现在将是：

    // ...
    int target = 19;
    int left = 0, right = li.length-1; // 1. fix value of right
    while (left < right) {
      int mid = left + (right - left) / 2; // 2. added left to mid
      if (li[mid] == target) {
        // ...

数组是零索引的，lengthreturns数组中元素的数量。元素本身，从 0 到 length-1。因此，right 被调整为包含最终元素的索引。您可以通过删除 -1 并将 target 设置为最后一个元素 30 来对此进行测试。这将导致错误。
mid 应该存储数组当前搜索部分的中间元素的索引。当前部分从 left 开始，到 right 结束。因此，要找到中间元素，我们使用 lower bound + (upper bound - lower bound) / 2.

Java 中的二进制搜索不会终止

Binary Search in Java does not terminate

java

binary-search