Arrays.BinarySearch需要数组按升序排列吗？

Question

根据文档显示：

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

使用二分查找算法在指定的数组中搜索指定的对象。 在进行此调用之前，根据指定的比较器（例如通过 sort(T[]，Comparator) 方法），必须按升序对数组进行排序。 如果未排序，则结果是未定义的。 如果数组包含多个等于指定对象的元素，则不能保证找到哪一个。

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）。

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

- ziggy

Answer 1

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

- Oliver Charlesworth

Answer 2

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

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

二分搜索是基于这个假设工作的。http://en.wikipedia.org/wiki/Binary_search_algorithm当它比较中间元素时，它可以假定如果该元素大于中间元素，它也大于中间前的所有元素。如果数组没有特定顺序，它将不得不搜索整个数组，也称为暴力搜索。

- Peter Lawrey

Answer 3

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

- Stuart Golodetz

---

我认为这就是让我感到困惑的原因。我理解描述的意思是比较器应该按升序对值进行排序，即a[0]<...<a[n-1]。 - ziggy