Двоичный (бинарный) поиск в массиве

Бинарный поиск - алгоритм, позволяющий очень быстро искать объект, удовлетворяющий определённым критериям, в упорядоченном множестве таких же объектов.

Идея

Пусть дан упорядоченный по неубыванию массив $a$ размера $n$ и число $x$, требуется найти первое вхождение числа $x$ в массив $a$ или сказать, что числа в массиве нет. Мысленно дополним массив: положим $a[-1] = -\infty, a[n] = +\infty$. Кроме этого, объявим две переменные $l=-1, r=n$, которые будут границами поиска.

В нашем алгоритме мы будем изменять границы $l, r$, поддерживая следующий инвариант: $a[l] < x, a[r] \geq x$.

Делать это будем, пока $r - l > 1$, следующим образом: объявим $m = \lfloor \dfrac{l+r}{2} \rfloor$.

Если $a[m] < x$, то присваиваем $l = m$, а иначе - $r = m$.

Реализация

Ниже приведена реализация данного алгоритма на языке python3

l, r = -1, n
while l + 1 < r:
    m = (l + r) // 2
    if a[m] < x:
        l = m
    else:
        r = m
if r < n and a[r] == x:
    print(x)
else:
    print(-1)

Корректность алгоритма

Заметим, что $r - l$, то есть длина отрезка, на котором мы ищем, каждый раз уменьшается примерно вдвое. Это значит, что рано или поздно она станет равной $1$, то есть $r - l = 1$, а значит, алгоритм завершится.

Раз мы сохраняли наш инвариант на протяжении всей работы, то он сохранится и после завершения, а значит, мы будем иметь $a[r - 1] < x, a[r] \geq x$.

Выходит, что $a[r]$ - первый элемент, не меньший $x$.

Если $a[r] = x$, то это и есть первое вхождение числа $x$. Если же $a[r] > x$, то $x$ не входит в массив: действительно, он упорядочен, а значит, все последующие числа не меньше $a[r]$, то есть больше $x$. Ну а все предыдущие будут меньше, ведь $a[r-1] < x$.

Асимптотика

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

Для начала будем считать, что длина каждую итерацию уменьшается строго вдвое: в таком случае $n = 2^p$ для какого-то натурального $p$. Если это не выполнено, то мы можем мысленнно дополнить массив до длины, равной степени двойки, увеличив его не более чем вдвое.

Несложно заметить, что в таком случае наш алгоритм делает ровно $p$ итераций.

Число $p$ называется двоичным логарифмом числа $n$ и обозначается так: $p = \log_2 n$. Более строго, $\log_b n$ это такое число, что $b^{\log_b n} = n$. Число $b$ называется основанием логарифма.

Оказывается, эта функция растёт очень медленно: к примеру, $2^{20} \approx 10^6$, значит, $\log_2 10^6 \approx 20$

Тогда асимптотика нашего алгоритма - $O(\log n)$.

В асимптотике не пишут основание логарифма: дело в том, что для перехода от основания $b_1$ к основанию $b_2$ необходимо домножить логарифм на константу $\log_{b_2} b_1$, а константы в $O$ не пишутся.

Во встроенных библиотеках

В C++ есть две стандартные функции: lower_bound() и upper_bound(). Они принимают указатели на начало и конец упорядоченного по неубыванию массива, а также число $x$. Первая возвращает указатель на первый элемент $>=x$, а вторая - на первый элемент $>x$.

Аналогичные функции есть в python3, они лежат в библиотеке bisect и называются bisect_left() и bisect_right(). Однако они возвращают индекс, а не указатель.

Если у нас есть, например, массив a = [1, 2, 2, 3, 4, 4, 4, 5, 7, 9, 9], то lower_bound(a.begin(), a.end(), 4) - a.begin() вернёт $4$, а upper_bound(a.begin(), a.end(), 4) - a.begin() - $7$.

Если мы для какого-нибудь $x$ посчитаем upper_bound(a.begin(), a.end(), x) - lower_bound(a.begin(), a.end(), x), то мы получим количество вхождений $x$ в данный массив.

Так, например, можно понять, что в массиве $a$ 3 вхождения числа $4$.