2

好的，伙计们，这是我的一段简单代码，我在其中构建了一个字符串数组并尝试在该数组中搜索一个字符串：

String[] arr = new String[5];
arr[0] = "ccc";
arr[1] = "aaa";
arr[2] = "bbb";
arr[3] = "eee";
arr[4] = "ddd";

System.out.println(Arrays.binarySearch(arr,"eee"));

直接取自 Java 6 binarySearch 文档：“在进行此调用之前必须对数组进行排序。如果未排序，则结果未定义”！

实际上，我多次运行我的代码，输出总是 3，这是我的未排序数组中 eee 的位置，但结果似乎不是“未定义”，如文档所述。

我错过了什么？

谢谢

4

6 回答 6

8

“未定义”并不意味着“肯定会给你错误的结果”，或者“肯定会崩溃”。

于 2012-05-07T20:28:21.423 回答
5

当我们谈论一段代码的行为时，术语“未定义”意味着程序执行可以做以下任何事情：

  • 返回错误答案
  • 永远循环
  • 立即崩溃
  • 损坏一些数据并在很久以后导致崩溃
  • 做一些意外的事情（例如擦除你的硬盘）
  • 幸运并返回正确答案

作为对程序员的建议，不要调用未定义的行为，因为任何事情都可能发生，无论好坏，现在或以后。

于 2012-05-07T20:30:56.267 回答
4

您错过了“结果未定义”包括“正确”答案的可能性，就像在这种情况下一样。

如果您将 arr[1] 更改为“eee”，您将看到不同的结果。

于 2012-05-07T20:28:12.083 回答
4

许多机构、书籍、教授等定义的二进制搜索要求元素以字母或数字方式排序。

import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    String[] arr = new String[6];
    arr[0] = "ccc";
    arr[1] = "aaa";
    arr[2] = "bbb";
    arr[3] = "eee";
    arr[4] = "ddd";
    arr[5] = "aaa";
    System.out.println(Arrays.toString(arr));
    System.out.println("\"eee\" was found at index: " + Arrays.binarySearch(arr, "eee"));
    Arrays.sort(arr);
    System.out.println(Arrays.toString(arr));
    System.out.println("\"eee\" was found at index: " + Arrays.binarySearch(arr, "eee"));
  }
}
于 2012-05-07T20:28:33.643 回答
3

“未定义”意味着算法将在您的数组上运行，但不能保证结果是正确的（二分搜索强烈需要排序数组才能工作）。您的示例有效，因为这就是发生的情况：

  • 输入二分搜索，第一个 = 0，最后一个 = 4，中间 = 2 比较
  • 数组[中间] 与 "eee" ("bbb"<"eee") => first = 2 + 1; 中间= 3；
  • 将 array[middle] 与 "eee" => "found" 进行比较；返回 3；
于 2012-05-07T20:32:08.883 回答
1

添加到esej的答案，这是您的程序的修改，它返回错误的答案：

public class Main {
    public static void main(String[] args) {
        String[] arr = new String[6];
        arr[0] = "ccc";
        arr[1] = "aaa";
        arr[2] = "bbb";
        arr[3] = "eee";
        arr[4] = "ddd";
        arr[5] = "aaa";

        System.out.println(Arrays.binarySearch(arr, "eee"));
    }
}
于 2012-05-07T20:28:51.337 回答