Поиск элемента в списке с использованием Collections.reverseOrder()

194

30 августа 2021, 23:10

    List al = new ArrayList();
    al.add(100);
    al.add(50);
    al.add(30);
    al.add(10);
    al.add(2);
    System.out.println("Found at index " + Collections.binarySearch(al, 100,Collections.reverseOrder()));
    List al0 = new ArrayList();
    al0.add(50);
    al0.add(100);
    al0.add(30);
    al0.add(10);
    al0.add(2);
    System.out.println("Found at index " + Collections.binarySearch(al0, 100,Collections.reverseOrder()));
    List al1 = new ArrayList();
    al1.add(30);
    al1.add(100);
    al1.add(10);
    System.out.println("Found at index " + Collections.binarySearch(al1, 100,Collections.reverseOrder()));
    List al2 = new ArrayList();
    al2.add(30);
    al2.add(20);
    al2.add(100);
    System.out.println("Found at index " + Collections.binarySearch(al2, 100,Collections.reverseOrder()));

Почему вывод поиска разный?

Found at index 0
Found at index -1
Found at index 1
Found at index -1

Хотелось понять почему не работает такая реализация поиска.

Понятно что необходимо предварительно произвести обычную сортировку Collections.sort(). Хотя первый и третий поиск успешный и без нее..

Answer 1

Если у вас массив отсортирован в обратном порядке, то можно использовать binarySearch с reverseOrder в качестве компаратора. Если массив не отсортирован - он может не находить элемент, который в массиве есть, потому что алгоритм бинарного поиска не учитывает такого случая. Но может и найти, если звезды сойдутся. Конкретно в ваших примерах:

Элемент нашелся, т.к. список отсортирован в обратном порядке и реверсивный же компаратор используется для поиска. binarySearch отрабатывает ровно так, как в это задумывается
Массив не отсортирован, потому 100 не находится. На первом шаге проверяется 30. Не совпало, отсекаем половину. Если бы не реверсивный компаратор, то на следующем шаге проверялся бы отрезок 10, 2, но реверсия заставляет проверять 50, 100. На втором шаге проверяется 50, т.к. оно меньше 100, алгоритм пытается взять левую чать, но левой части нет. Потому решает что и 100 нет в массиве и возвращает -1.
Массив не отсортирован, но т.к. искомый элемент находится в середине, то он находится на первой же итерации. Был бы он не на середине - не нашелся бы
Массив отсортирован не в том порядке. Он найдет середину, это 20. Если бы вы не отдавали бы реверсивный компаратор то алгоритм решил бы, что искомое во второй половине, но вы передали реверсивный. Поэтому он начинает искать в первой. Проверяет 30, видит что это не то и возвращает -1

Answer 2

По порядку Хотя первый и третий поиск успешный и без нее.. Первый список нашел ответ корректно, потому что он отсортирован, вы используете реверс ордер. Третий список наше верно, потому что бинарный поиск сразу попал в него.

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