5. Двоичный поиск

Двоичный поиск

Если элементы массива расположены в возрастающем порядке (то есть массив отсортирован), то искать элемент в массиве можно быстрее, чем за линейное время.

Пусть мы хотим найти $x$ в отсортированном массиве $a$ длины $n$. Снова применим идею метода “разделяй и властвуй”: посмотрим на элемент в середине массива - $a\left[\frac{n}{2}\right]$. Если $a\left[\frac{n}{2}\right]=x$, то мы нашли $x$ в массиве $a$. Если $a\left[\frac{n}{2}\right]>x$, то $x$ может найтись только в $a\left[0,1, \ldots, \frac{n}{2}-1\right]$. Если же $a\left[\frac{n}{2}\right] < x$, то $x$ может найтись только в $a\left[\frac{n}{2}+1, \ldots, n-1\right]$. В любом из последних двух случаев, мы вдвое уменьшили длину отрезка, на котором нужно искать $x$.

Теперь можно рекурсивно повторить те же рассуждения - посмотреть на середину нового подоотрезка массива, и либо в середине найдётся $x$, либо мы поймём, в какой половине нового подотрезка нужно его искать. Будем повторять эти действия, пока не найдём $x$, либо не дойдём до подотрезка нулевой длины. Поскольку на каждом шаге длина отрезка уменьшается вдвое, это произойдёт через $O(\log n)$ шагов.

Также можно оценить время работы нашего алгоритма с помощью основной теоремы о рекуррентных соотношениях: время работы алгоритма в худшем случае (когда $x$ так и не нашёлся, либо нашёлся в самом конце) удовлетворяет рекуррентному соотношению $T(n)=T\left(\frac{n}{2}\right)+\Theta(1)$. Это соответствует $a=1, b=2, c=0$ в формулировке теоремы. $c=0=\log _{2} 1=\log _{b} a$, тогда по теореме время работы алгоритма в худшем случае есть $\Theta(\log n)$.

Примерная реализация алгоритма двоичного поиска:

binarySearch(a, n, x): # ищет x в массиве а длины n, возвращает индекс,
                                    # по которому лежит x, или -1, если х в массиве нет
    l = 0, r = n - 1 # границы интересующего нас подотрезка массива
    while l <= r: # пока подотрезок непуст
        m = (l + r) / 2
        if a[m] == x:
            return m
        if a[m] < x:
            l = m + 1
        else:
            r = m - 1
    return -1 # x так и не нашёлся

Левое вхождение

Возможно, $x$ встречается в массиве несколько раз (так как массив отсортирован, эти вхождения образуют подотрезок массива). Научимся находить количество вхождений $x$ в массив (то есть длину этого подотрезка).

Достаточно найти индексы самого левого и самого правого вхождений $x$ в массив, тогда количество вхождений - это разность этих индексов плюс один. Начнём с левого вхождения.

Будем снова поддерживать границы $l$ и $r$, но уже со следующим условием: пусть в любой момент времени выполняется $a[l]< x$ и $a[r] \geqslant x$. Удобно мысленно добавить к массиву фиктивные элементы $a[-1]=-\infty$ и $a[n]=\infty$, тогда не нужно отдельно обрабатывать случаи, когда все элементы меньше $x$, или все элементы больше или равны $x$.

Сам алгоритм становится только проще: смотрим на середину отрезка $(l, r)$, и, в зависимости от значения элемента массива с этим индексом, сдвигаем $l$ или $r$ так, чтобы требуемые от них условия не нарушились. Когда $l$ и $r$ указывают на соседние элементы (то есть $l=r-1$ ), всё ещё верно, что $a[l] < x, a[r] \geqslant x$. Тогда если $a[r]=x$, то $r$ индекс левого вхождения $x$, иначе $x$ в массиве не встречается.

Примерная реализация:

lowerBound(a, n, x): # возвращает минимальное i такое, что a[i] >= x
    l = -1, r = n # l и r изначально указывают на фиктивные элементы
    while r - l > 1:
        m = (l + r) / 2
        if a[m] < x:
            l = m # условие на l не нарушилось
        else:
            r = m # условие на r не нарушилось
    return r
getLeftEntry(a, n, x): # возвращает номер левого вхождения или -1
    i = lowerBound(a, n, x)
    if i == n or a[i] != x:
        return -1
    return i

Правое вхождение ищется примерно так же: нужно требовать от границ поиска $a[l] \leqslant x$ и $a[r]>x$, тогда в конце $l$ - правое вхождение, если $a[l]=x$, иначе $x$ в массиве не встречается. Заметим, что в реализации самого поиска нужно поправить всего одну строчку: a [m] < x заменить на $\mathrm{a}[\mathrm{m}]$ <= x .

В C++ есть встроенные функции std::lower_bound и std::upper_bound. Первая возвращает итератор, указывающий на первый элемент, больше или равный $x$, вторая на первый элемент, строго больший $x$. Пример использования:

i = lower_bound(a, a + n, x) - a;
// минимальное i такое, что a[i] >= x; n, если все элементы а меньше х
i = upper_bound(a, a + n, x) - a;
// минимальное i такое, что a[i] > x; n, если все элементы а меньше или равны х
i = upper_bound(a, a + n, x) - a - 1;
// максимальное i такое, что a[i] <= x; -1, если все элементы а больше х
cnt = upper_bound(a, a + n, x) - lower_bound(a, a + n, x);
// количество вхождений х в а

Двоичный поиск по функции

Можно рассмотреть и ещё более общую версию алгоритма. Пусть есть некоторая функция $f(i)$ такая, что $f(i)=0$ для всех $i$, меньших некоторого порога $t$, и $f(i)=1$ для всех $i \geqslant t$. Тогда этот порог можно найти с помощью алгоритма двоичного поиска.

Идея та же, что и при поиске левого вхождения: сначала возьмём такие границы поиска $l=L, r=R$, что $f(L)=0, f(R)=1$. После этого на каждом шаге будем сдвигать одну из границ $l, r$, в зависимости от значения $f\left(\frac{l+r}{2}\right)$. В тот момент, когда $l$ и $r$ отличаются на единицу, $r$ - искомый порог. Если считать, что значение функции в точке вычисляется за $O(1)$, то время работы алгоритма $-O(\log (R-L))$, где $L, R-$ начальные границы поиска.

Заметим, что алгоритмы поиска левого и правого вхождения являются частными случаями этого алгоритма: в случае левого вхождения можно взять функцию $f$ такую,

что $f(i)=1$ тогда и только тогда, когда $a[i] \geqslant x$; в случае правого вхождения $-f(i)=1$ тогда и только тогда, когда $a[i]>x$ (и нас интересует максимальное $i$ такое, что $f(i)=0$, то есть в конце алгоритма нужно вернуть $l$, а не $r$ ).

Двоичный поиск по функции с вещественным аргументом

Двоичный поиск можно делать и по функции, принимающей значения во всех вещественных точках, а не только в целых. Решим для примера такую задачу: дана монотонно возрастающая непрерывная функция $f: \mathbb{R} \rightarrow \mathbb{R}$, и точки $L, R$ такие, что $f(L)<0$, $f(R) \geqslant 0$. Найдём точку $x$ такую, что $f(x)=0$. (R)

Если такие $L, R$ не даны, но известно, что они существуют, то их можно найти алгоритмом экспоненциального поиска: начнём с $R=1$ и будем удваивать $R$, пока $f(R)<0$. Аналогично, начнём с $L=-1$ и будем удваивать $L$, пока $f(L) \geqslant 0$. При этом мы затратим $O\left(\log \left|R^{\prime}\right|+\log \left|L^{\prime}\right|\right)$ действий, где $R^{\prime} \geqslant 0, L^{\prime} \leqslant 0-$ любые такие, что $f\left(L^{\prime}\right)<0, f\left(R^{\prime}\right) \geqslant 0$.

Поскольку $f$ принимает вещественные значения, мы не всегда можем найти значение такого $x$ абсолютно точно. Тем не менее, мы можем найти такое $x$ с погрешностью $\varepsilon$ : найдём такое $x$, что существует $x^{\prime}$ такое, что $f\left(x^{\prime}\right)=0,\left|x-x^{\prime}\right|<\varepsilon$.

Алгоритм практически не меняется: начинаем с границ $l=L, r=R$, на каждом шаге сдвигаем одну из границ в зависимости от значения $f\left(\frac{l+r}{2}\right)$. Единственное отличие: мы завершаем алгоритм в тот момент, когда $r-l<\varepsilon$. Поскольку в этот момент всё ещё $f(l)<0, f(r) \geqslant 0$, а функция $f$ непрерывна, на отрезке $[l, r]$ найдётся $x^{\prime}$ такое, что $f\left(x^{\prime}\right)=0$. Поскольку длина отрезка меньше $\varepsilon$, любая из границ $l, r$ подойдёт в качестве ответа. Время работы алгоритма (при условии, что значение $f$ вычисляется за $O(1)$ ) $O\left(\log \left(\frac{R-L}{\varepsilon}\right)\right)$.

Если вычисления проводятся при помощи стандартных вещественнозначных типов данных (например, double в C++), то из-за накопления погрешности при пересчёте границ условие $r-l<\varepsilon$ может никогда не выполниться. Чтобы избежать этого, вместо while напишем цикл, делающий столько итераций, сколько нужно, чтобы условие точно выполнилось. Пример реализации:

findRoot(L, R, eps):
    l = L, r = R
    k = log((r - l) / eps) # через k итераций условие r - l < eps выполнится
    for i = 0..(k - 1):
        m = (l + r) / 2
        if f(m) < 0:
            l = m # условие на l не нарушилось
        else:
            r = m # условие на r не нарушилось
    return r

Метод двух указателей

Иногда много двоичных поисков на одних и тех же данных можно соптимизировать с помощью так называемого метода двух указателей. Сделаем это на примере следующей задачи: дан массив $a$ длины $n$, состоящий из неотрицательных целых чисел. Нужно найти максимальный по длине подотрезок массива, сумма на котором не превосходит $M$.

Удобнее работать не с отрезками, а с полуинтервалами: паре $l, r$ будем сопоставлять полуинтервал $a[l, r)$, то есть элементы массива с индексами $l, l+1, \ldots, r-1$ (это практически всегда позволяет писать меньше плюс-минус единиц в индексах массивов, что делает код короче). Самое простое решение - перебрать все возможные полуинтервалы:

maxLen = 0, ansL = 0, ansR = 0 # здесь будем хранить ответ
for l = 0..(n - 1): # перебираем левую границу
    sum = 0 # будем считать сумму на текущем полуинтервале
    for r = (l + 1)..n:
        sum += a[r - 1]
        if sum <= M and r - l > maxLen:
            maxLen = r - l, ansL = l, ansR = r

Получилось решение за $\Theta\left(n^{2}\right)$. Заметим, что при фиксированной левой границе сумма на полуинтервале не уменьшается при увеличении правой границы. Значит сколькото первых правых границ подойдут, а все последующие уже не подойдут. При этом нас интересует максимальная подходящая правая граница. Её можно найти двоичным поиском, таким образом соптимизировав решение до $\Theta(n \log n)$ :

Для того, чтобы быстро находить сумму на произвольном полуинтервале, заранее предподсчитаем префиксные суммы - массив $p$ такой, что $p[i]=\sum_{j=0}^{i-1} a_{j}$. Тогда сумма на полуинтервале $a[l, r)$ равна $\sum_{i=l}^{r-1} a_{i}=p[r]-p[l]$.

maxLen = 0, ansL=0, ansR = 0
int p[n + 1] # предподсчитываем префиксные суммы
p[0] = 0
for i = 1..n:
    p[i] = p[i - 1] + a[i - 1]
for l = 0..(n - 1):
    sl = l, sr = n + 1 # границы поиска, sum a[l..sl) <= M, sum a[l..sr) > M
    while sr - sl > 1:
        sm = (sl + sr) / 2
        if p[sm] - p[l] <= M:
            sl = sm
        else:
            sr = sm
    if sl - l > maxLen: # sl - максимальная подходящая правая граница
        maxLen = sl - l, ansL = l, ansR = sl

Перейдём теперь собственно к методу двух указателей. Пусть $r$ - максимальная подходящая правая граница для левой границы $l-1$. Тогда $M \geqslant \sum_{i=l-1}^{r-1} a_{i} \geqslant \sum_{i=l}^{r-1} a_{i}$, то есть граница $r$ подойдёт и для $l$. Будем вместо двоичного поиска искать границу $r$ так же, как и в самой первой версии алгоритма: просто перебирая все границы подряд. Но начнём перебор не с $l+1$, а с правой границы, найденной на предыдущем шаге. Поскольку теперь правая граница только увеличивается в ходе алгоритма, суммарно за всё время выполнения алгоритма она сдвинется не более, чем $n$ раз. Тогда общее время работы алгоритма $-\Theta(n)$.

maxLen = 0, ansL=0, ansR = 0
r = 0, sum = 0
for l = 0..(n - 1): # перебираем левую границу
    while r < n and sum + a[r] <= M:
        sum += a[r]
        r += 1
    if sum <= M and r - l > maxLen:
        maxLen = r - l, ansL = l, ansR = r
    sum -= a[l]