4

根据文档：

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

使用二分搜索算法在指定数组中搜索指定对象。

在进行此调用之前，必须根据指定的比较器（如通过 sort(T[], Comparator) 方法）对数组进行升序排序。

如果未排序，则结果未定义。如果数组包含多个等于指定对象的元素，则无法保证会找到哪一个。

上面是不是意味着该Arrays.binarySearch方法只能在Array升序排序时使用？

我测试了它，如下所示

class Unturned {
    public static void main(String[] args) {
        String[] chars = {"a", "b", "c", "e","f","h","i"};
        MySort ms = new MySort();

        Arrays.sort(chars, ms);
        for(String c : chars ) System.out.print(c + " ");

        System.out.println("\n" + Arrays.binarySearch(chars, "d", ms));
    }
    static class MySort implements Comparator<String> {
        public int compare(String a, String b) {
            return b.compareTo(a);
} } }

输出：

i h f e c b a
-5

-5 将插入点放在值为 c 的元素上，这是正确的。（即-4-1）。
为什么文档说数组必须按升序排序？

4

3 回答 3

5

它说“必须根据指定的比较器升序排序”。粗体部分是关键部分；您的数组确实根据指定的比较器进行了排序（因为您刚刚对它进行了排序！）。

于 2012-01-02T18:28:30.087 回答
4

它要求所有元素都根据 Comparator 的实现方式增加。例如，您使用反向比较器，所有元素都必须以相反的顺序排列。

为什么文档说数组必须按升序排序？

二进制搜索基于此假设工作。http://en.wikipedia.org/wiki/Binary_search_algorithm当它比较中间元素时，它可以假设如果它大于那个元素，它也大于中间之前的所有元素。如果数组没有特定顺序，则必须搜索整个数组，也称为蛮力搜索。

于 2012-01-02T18:28:50.903 回答
3

每个比较器定义给定类型元素的排序。要求仅仅是对数组元素进行排序，使得 a[0] < ... < a[n-1] 对于 < 的某些有效定义。该定义不必对应于我们对数字的传统概念< ——事实上，它甚至可以被定义为传统的>。

于 2012-01-02T18:34:32.797 回答