Бинарный поиск

Зачем массиву быть отсортированным

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

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

Инвариант: кандидат и замкнутый интервал

Оставшийся интервал поиска включает обе границы: [low, high]. До low находятся значения строго меньше искомого. Кандидат — уже найденное равное значение; внутри интервала ещё может находиться более раннее вхождение.

Если values[mid] < target, переносим low на mid + 1. Иначе переносим high на mid − 1; при равенстве предварительно сохраняем mid как кандидата. Каждый проход исключает mid и хотя бы половину текущего интервала. Когда low > high, возвращаем кандидата или −1.

Пример с повторяющимися шестёрками

В исходном массиве из 16 элементов первая середина — индекс 7 со значением 6. Сохраняем индекс 7, но не останавливаемся: слева может быть ещё одна шестёрка. Далее проверяем индексы 3, 5 и 4. Ответ — индекс 5, всего проверено четыре элемента.

Попробуйте найти 7, которого нет в массиве, −8 в начале или 34 в конце. Пустой массив возвращает −1 без проверок элементов. Счётчик учитывает проверенные средние элементы, а не отдельные операторы сравнения JavaScript.

Время и память

Средняя и худшая временная сложность — O(log n), для пустого входа — O(1). Этот вариант продолжает искать после равенства, поэтому совпадение в середине не означает немедленного завершения. Итеративный поиск использует O(1) дополнительной памяти и не меняет массив.

Визуализатор один раз копирует вход и разделяет этот замороженный массив между неизменяемыми снимками. История занимает O(n + log n) памяти — отдельно от самого алгоритма. Проверка входа занимает O(n). Стабильность — свойство сортировки; поиск не переставляет равные элементы.

Реализация на JavaScript

Функция ниже использует те же границы, середину и обработку повторов, что и визуализация. На входе ожидаются отсортированный массив конечных чисел и конечное искомое число. Результат — индекс с нуля или −1, если совпадений нет.

function binarySearchFirst(values, target) {
    let low = 0;
    let high = values.length - 1;
    let result = -1;
    while (low <= high) {
        const mid = low + Math.floor((high - low) / 2);
        if (values[mid] < target) {
            low = mid + 1;
        } else {
            if (values[mid] === target) result = mid;
            high = mid - 1;
        }
    }
    return result;
}

За что отвечает AlgiViz

Алгоритм и его состояния определены на сайте. AlgiViz предоставляет неизменяемые оболочки шагов, временную шкалу и отрисовку сцены. Плеер возвращается к сохранённым шагам без повторного запуска поиска. На canvas подсветка меняется дискретно: для понимания шага движение не требуется.