Требуется ли Arrays.BinarySearch, чтобы массив был отсортирован в порядке возрастания

Согласно документации:

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

Ищет в указанном массиве указанный объект, используя алгоритм двоичного поиска.

Массив должен быть отсортирован в порядке возрастания в соответствии с указанным компаратором (как метод sort(T[], Comparator)) перед выполнением этого вызова.

Если он не отсортирован, результаты не определены. Если массив содержит несколько элементов, равных указанному объекту, нет гарантии, какой из них будет найден.

Означает ли вышеизложенное, что метод Arrays.binarySearch можно использовать только тогда, когда массив отсортирован в возрастающем порядке?

Я проверил это, как показано ниже

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).
Почему в документации говорится, что массив должен быть отсортирован в порядке возрастания?


java string oop scjp
person ziggy    schedule 02.01.2012    source источник

Ответы (3)


arrow_upward
3
arrow_downward

Каждый компаратор определяет порядок элементов данного типа. Требование состоит лишь в том, что элементы массива должны быть отсортированы таким образом, что a[0] ‹ ... ‹ a[n-1] для некоторого допустимого определения ‹. Это определение не обязательно должно соответствовать нашему общепринятому понятию ‹, например. числа -- на самом деле, это можно было бы даже определить как обычное >.

person Stuart Golodetz    schedule 02.01.2012
comment
Я думаю, это то, что меня смутило. Я интерпретировал описание как означающее, что компаратор должен сортировать значения в порядке возрастания, то есть a[0]‹...‹a[n-1] - person ziggy; 02.01.2012

arrow_upward
5
arrow_downward

В нем говорится, что «должен быть отсортирован в порядке возрастания в соответствии с указанным компаратором». Часть, выделенная жирным шрифтом, является важной частью; ваш массив действительно отсортирован в соответствии с указанным компаратором (потому что вы только что его отсортировали!).

person Oliver Charlesworth    schedule 02.01.2012

arrow_upward
4
arrow_downward

Это требует, чтобы все элементы увеличивались в зависимости от того, как реализован Компаратор. например вы используете обратный компаратор, все элементы должны быть в обратном порядке.

Почему в документации говорится, что массив должен быть отсортирован в порядке возрастания?

Бинарный поиск работает на основе этого предположения. http://en.wikipedia.org/wiki/Binary_search_algorithm Когда он сравнивает средний элемент, он может предположим, что если он больше этого элемента, он также больше всех элементов до середины. Если бы массив не был в определенном порядке, ему пришлось бы искать весь массив, что также называется поиском методом грубой силы.

person Peter Lawrey    schedule 02.01.2012