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

Бинарный поиск (binary search) находит элемент в отсортированном массиве, на каждом шаге отбрасывая половину: $O(\log N)$ вместо $O(N)$ у перебора. Та же идея работает для монотонной функции — это бинарный поиск по ответу.

Зачем нужно

Проверить, есть ли key в массиве, можно перебором — линейным поиском:

flag = false
for i = 0 ... N
    если arr[i] = key
        flag = true
        вывести(i)
        break
если flag = false
    вывести("не нашёл")

$T(N)=O(N)$, $M(N)=O(1)$. Быстрее нельзя, пока о массиве ничего не известно. Если же массив отсортирован — $a[0]\le a[1]\le \cdots \le a[N-1]$ — одно сравнение с серединой сразу говорит, в какой половине искать.

При $N\sim 10^{12}$: перебор — $10^{12}$ итераций, около $10^4$ секунд; бинарный поиск — ${\log }_{2}10^{12}\approx 40$ итераций.

Граница в линейном поиске

Индексы — от 0 до $N-1$. Если for i = 0 ... N включает N, это обращение за пределы массива, в C++ — Неопределённое поведение.

Как работает

• $key<arr[M]$ ⇒ искомое в левой половине;
• $key>arr[M]$ ⇒ в правой.

L = 0
R = N - 1
пока (R - L > 1) {
    M = (L + R) / 2          // в C++: M = L + (R - L) / 2
    если arr[M] > key
        R = M
    иначе если arr[M] < key
        L = M
    иначе
        L = M
        break
}
если arr[L] = key или arr[R] = key
    вывести("нашли")
иначе
    вывести("не нашли")

Цикл сужает отрезок, пока в нём больше двух элементов. Оставшиеся два соседних кандидата проверяются после цикла.

Не из лекции: доказательство правильности

Инвариант: если key есть в массиве, он среди $arr[L],\dots ,arr[R]$.

• Вначале это весь массив.
• arr[M] > key: из сортировки $arr[i]\ge arr[M]>key$ при $i\ge M$, искомое в $[L,M-1]\subset [L,M]$.
• arr[M] < key: симметрично, в $[M+1,R]\subset [M,R]$.
• arr[M] = key: найден, L = M, проверка после цикла его увидит.

Остановка: при $R-L>1$ середина строго внутри, $L<M<R$, и $R-L$ строго уменьшается.

Ответ: после цикла $R-L\le 1$ — кандидатов только два, и по инварианту искомое, если оно есть, среди них.

Асимптотика

Длина отрезка: $N\to N/2\to N/4\to \cdots \to N/2^k$. Остановка при $N/2^k=1$, то есть $k={\log }_{2}N$: $T(N)=O(\log N)$, $M(N)=O(1)$.

Не из лекции: аккуратно

При $d=R-L$ части отрезка — $\lfloor d/2\rfloor$ и $\lceil d/2\rceil$, новое $d\le \lceil d/2\rceil$. Шагов до $d\le 1$ — не больше $\lceil {\log }_{2}N\rceil$. Почему основание логарифма в оценке не пишут — см. Асимптотические оценки.

Почему L + (R − L) / 2

На лекции отмечено: в C++ середину пишут как M = L + (R − L) / 2.

Не из лекции: причина

L + R при индексах около $2\cdot 10^9$ не помещается в int (максимум $2147483647$). Переполнение знакового целого — UB, см. Неопределённое поведение и Целочисленные типы. R − L лежит между 0 и R и переполниться не может. Для $L,R\ge 0$ результат тот же: $\lfloor (L+R)/2\rfloor =L+\lfloor (R-L)/2\rfloor$.

Бинарный поиск по ответу

Обычный бинарный поиск ищет число в массиве, поиск по ответу — число, но в функции. Если $f(x)$ монотонна на $[L,R]$, её значения упорядочены, как отсортированный массив: $arr[x]\leftrightarrow f(x)$. Середина отрезка по $x$ и сравнение $f(M)$ с целью говорят, в какой половине ответ.

Пример: $\sqrt{N}$

$\sqrt{N}=M⟺M^2=N$. Функция $M^2$ монотонна при $M\ge 0$.

float L = 0, R = N
eps = 10^-5
пока (|L*L - N| > eps) {
    M = (L + R) / 2
    если M*M < N
        L = M
    иначе
        R = M
}

Второй вариант — с гарантированным числом итераций:

float L = 0, R = N
for i = 0 ... 1000
    M = (L + R) / 2
    если M*M < N
        L = M
    иначе
        R = M

Не из лекции: инвариант и границы

Инвариант: $L^2<N\le R^2$, то есть $\sqrt{N}\in [L,R]$. Каждая ветка сохраняет свою половину неравенства, отрезок уменьшается вдвое.

Граница $R=N$ годится только при $N\ge 1$: из $N\le N^2$ следует $\sqrt{N}\le N$. При $0<N<1$ корень больше самого числа ($\sqrt{0,25}=0,5$), и нужна $R=\max (1,N)$.

Почему вариант с eps опасен на дробных числах и сколько итераций из 1000 реально работают — проверено в конспекте лекции и объяснено в Типы с плавающей точкой.

Тонкости

• Массив обязан быть отсортирован. На неотсортированном бинарный поиск не падает, а просто отвечает неверно.
• Пустой массив ($N=0$) даёт $R=-1$: проверка arr[L] после цикла обратится к несуществующему элементу. Его проверяют до поиска.
• Для поиска по ответу нужна монотонность. Без неё отбрасывание половины ничем не обосновано.

Частые ошибки

• Считать середину как (L + R) / 2 на больших индексах в C++.
• Искать дробный ответ «до точности eps» на float: цикл может не остановиться.
• Не проверить после цикла оба оставшихся элемента — и arr[L], и arr[R].

Углубление — АиСД L03

Бинарный поиск назван среди применений сортировки: чтобы искать за $O(\log N)$, массив сначала сортируют.

Не из лекции: когда это выгодно

Сортировка дороже одного линейного поиска. Выгода появляется, когда запросов много: отсортировать один раз, а потом отвечать на каждый запрос за $O(\log N)$ вместо $O(N)$.

Расхождение с L02

Было (L02): «Индексы — от 0 до $N-1$. Если for i = 0 ... N включает N, это обращение за пределы массива».

В L03 и L04: запись 0 ... N в сортировках означает полуинтервал $[0,N)$ — иначе пузырёк с j = 0 ... N−i−1 и arr[j+1] выходил бы за массив, а MergeSort вызывается как (arr, 0, N, buffer) для arr[0; N). При таком чтении линейный поиск из L02 за массив не выходит.

Но запись непостоянна: в решете Эратосфена (L03) 2 ... N включает N, в проверке на простоту (L01) 1 ... p включает p. Предупреждение в L02 верно только при включающем чтении. Решение — за пользователем.