Краткий ответ

Корректность результата бинарного поиска определяется тем, отсортирован ли список в точности по тому же порядку, который использует поиск: по естественному порядку или по переданному Comparator. Если это условие нарушено, результат не гарантирован: метод может не найти существующий элемент или вернуть неверную позицию.

Исторический контекст

Бинарный поиск появился как способ находить элементы в упорядоченной последовательности за логарифмическое число сравнений, не просматривая список полностью. В Java Collections Framework этот подход доступен через Collections.binarySearch.

Цена эффективности — предварительное соблюдение строгого условия: элементы должны быть упорядочены относительно того же правила сравнения. Без этого алгоритм теряет основание для выбора, какую половину списка исключить.

Постановка проблемы

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

В такой ситуации линейный поиск обычно продолжил бы проверять элементы и мог бы найти совпадение. Бинарный поиск делает выводы о расположении цели по результатам сравнений, поэтому нарушенный контракт приводит к непредсказуемому с точки зрения вызывающего кода результату.

Подробное решение

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

При отсутствии компаратора применяется естественный порядок через Comparable. При наличии компаратора именно он определяет порядок и эквивалентность для целей поиска; его правила должны соответствовать сортировке списка.

Если элемент найден, метод возвращает индекс совпадения. Если элемент отсутствует, возвращается отрицательное значение, кодирующее позицию вставки. При нарушении сортировки нельзя надёжно интерпретировать ни найденный индекс, ни позицию вставки.

Сложность поиска обычно составляет O(log n) по числу сравнений. Однако для последовательных структур, например LinkedList, перемещение к середине может потребовать линейного времени, поэтому практическая стоимость может достигать O(n); для списков с быстрым произвольным доступом, таких как ArrayList, бинарный поиск сохраняет близкую к O(log n) общую сложность.

import java.util.*;

List<String> names = new ArrayList<>(List.of("Ann", "Bob", "Christopher"));
Comparator<String> byLength = Comparator.comparingInt(String::length);
names.sort(byLength);

int index = Collections.binarySearch(names, "Bob", byLength);
System.out.println(index);

Здесь сортировка и поиск используют один и тот же компаратор. Если отсортировать список по длине, а выполнить поиск без компаратора, контракт метода будет нарушен, даже если отдельный вызов случайно вернёт ожидаемый индекс.

Ситуация из практики

Сервис хранит список тарифов, отсортированный по числовому приоритету, и часто ищет тариф по этому приоритету. Разработчик применил бинарный поиск с естественным порядком объектов, хотя список был отсортирован отдельным компаратором по приоритету.

Рассматривались три варианта:

выполнять линейный поиск — просто и корректно, но O(n) при каждом запросе;
сортировать и искать по естественному порядку — возможно только если этот порядок действительно соответствует бизнес-правилу;
использовать один явно определённый компаратор и при сортировке, и при поиске — требует дисциплины, но сохраняет корректность и логарифмическую сложность для ArrayList.

Выбран третий вариант: компаратор сделали общей частью логики доступа к данным. Это устранило случайные промахи поиска и сохранило низкую стоимость частых запросов.

Что кандидаты часто упускают

1. Достаточно ли передать тот же компаратор в бинарный поиск, если список после сортировки изменился?

Нет. Компаратор задаёт правило порядка, но не сортирует список автоматически. После добавления или изменения элементов порядок может быть нарушен, поэтому перед новым поиском требуется восстановить сортировку либо использовать структуру, поддерживающую порядок при изменениях.

2. Гарантирует ли бинарный поиск конкретный индекс, если в списке есть несколько равных элементов?

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

3. Можно ли считать два компаратора одинаковыми, если они возвращают одинаковый порядок на текущих данных?

Для конкретного текущего списка результат может совпасть, но этого недостаточно как общего контракта. Важно, чтобы список был отсортирован по отношению, которое фактически использует поиск, на всех элементах, участвующих в операции; совпадение на небольшой выборке не гарантирует корректность при других данных.