Бинарный поиск
Находим число в отсортированном массиве, отбрасывая половину зоны поиска на каждом шаге.
1function binarySearch(arr: number[], target: number): number {2 let lo = 03 let hi = arr.length - 14 5 while (lo <= hi) {6 const mid = Math.floor((lo + hi) / 2)7 8 if (arr[mid] === target) return mid9 10 if (arr[mid] < target) {11 lo = mid + 112 } else {13 hi = mid - 114 }15 }16 17 return -118}Проблема
Как найти одно число среди миллиона, проверив всего около 20 позиций? Единственное условие — массив отсортирован. Линейный проход проверяет элементы по очереди (до миллиона проверок), бинарный поиск каждый раз делит зону поиска пополам.
Что вы видите
Массив — полка с числами. Зона поиска — подсвеченный диапазон полки. Три указателя: lo (левая граница), mid (середина), hi (правая граница). На каждом шаге середина сравнивается с целью, и половина зоны гаснет — она точно не содержит ответ.
Как это работает
Делим зону поиска пополам и спрашиваем: цель левее или правее середины? Отсортированность гарантирует, что весь кусок по ненужную сторону можно выбросить целиком. За log₂(n) делений зона схлопывается до одного элемента: либо нашли, либо числа нет.
Пошаговый разбор
- 01
Зона — весь массив
lo = 0, hi = n−1: ответ может быть где угодно.
- 02
Смотрим середину
mid = ⌊(lo+hi)/2⌋. Сравниваем arr[mid] с целью.
- 03
Выбрасываем половину
Цель больше — двигаем lo вправо от mid. Меньше — hi влево от mid.
- 04
Повторяем
Каждая итерация удваивает «плотность» поиска: зона сжимается экспоненциально.
- 05
Стоп
lo > hi — зона пуста, значения нет. Или arr[mid] = цель — индекс найден.
Complexity и ограничения
Массив обязан быть отсортирован. Работает на любых сравнимых данных (числа, строки — по порядку).
Edge cases
- Пустой массив
lo > hi сразу — возвращаем −1, ни одного сравнения.
- Цель меньше/больше всех
Зона съедается с одной стороны за log n шагов.
- Дубликаты
Классическая реализация возвращает любой из подходящих индексов.
Где встречается в реальности
Git bisect
Поиск коммита, сломавшего сборку: checkout середины истории, log n переборов вместо полного прохода.
Индексы БД
B-tree устроен как многоуровневый бинарный поиск: поиск строки по индексу — единицы дисковых страниц.
Словарь
Человек ищет слово в бумажном словаре примерно так же: открывает середину и решает, в какую сторону листать.
Связанные алгоритмы
«Как найти одно число среди миллиона, проверив всего ~20 позиций?»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.