Почему бинарный поиск в структуре Javas Collections использует итератор для поиска элемента в большом списке

Question

В документации по Java: -

Выполняет поиск в указанном списке указанного объекта с использованием алгоритма двоичного поиска. Список должен быть отсортирован в порядке возрастания в соответствии с {@linkplain Comparable natural ordering} его элементов (как методом {@link #sort (List)}) перед выполнением этого вызова. Если он не отсортирован, результаты не определены. Если список содержит несколько элементов, равных указанному объекту, нет гарантии, какой из них будет найден.

Этот метод выполняется за время log (n) для списка «произвольного доступа» (который обеспечивает позиционный доступ почти в постоянное время). Если указанный список не реализует интерфейс {@link RandomAccess} и имеет большой размер, этот метод будет выполнять двоичный поиск на основе итератора, который выполняет O (n) обход ссылок и O (log n) сравнения элементов.

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

public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

Answer 1

Ну, просто продолжайте смотреть на исходный код, все это довольно хорошо объяснено.
Ищите поле BINARYSEARCH_THRESHOLD static.

/*
 * Tuning parameters for algorithms - Many of the List algorithms have
 * two implementations, one of which is appropriate for RandomAccess
 * lists, the other for "sequential."  Often, the random access variant
 * yields better performance on small sequential access lists.  The
 * tuning parameters below determine the cutoff point for what constitutes
 * a "small" sequential access list for each algorithm.  The values below
 * were empirically determined to work well for LinkedList. Hopefully
 * they should be reasonable for other sequential access List
 * implementations.  Those doing performance work on this code would
 * do well to validate the values of these parameters from time to time.
 * (The first word of each tuning parameter name is the algorithm to which
 * it applies.)
 */
private static final int BINARYSEARCH_THRESHOLD   = 5000;

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

iteratorBinarySearch // or
indexedBinarySearch

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