Требует ли Arrays.BinarySearch сортировки массива в порядке возрастания - PullRequest
Новая
       22

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

4 голосов
/ 02 января 2012

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

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);
} } }

output: 

i h f e c b a
-5

-5 помещает точку вставки в элемент со значением c, которое является правильным.(т.е. -4-1).
Почему в документации говорится, что массив должен быть отсортирован в порядке возрастания?

Ответы [ 3 ]

5 голосов
/ 02 января 2012

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

4 голосов
/ 02 января 2012

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

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

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

3 голосов
/ 02 января 2012

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

...