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)$.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def binary_search(a, x):
    """
    Ищет x в отсортированном массиве a
    Возвращает индекс, по которому лежит x, или -1, если x в массиве нет
    """
    l = 0
    r = len(a) - 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 так и не нашёлся

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int binarySearch(int a[], int n, int x) {
    int l = 0, r = n - 1;  // границы интересующего нас подотрезка массива
    
    while (l <= r) {  // пока подотрезок непуст
        int m = l + (r - l) / 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$ в массиве не встречается.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

def getLeftEntry(a, x):
    """
    возвращает номер левого вхождения или -1
    """
    i = lowerBound(a, x)
    if i == len(a) or a[i] != x:
        return -1
    return i

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <vector>

int lowerBound(const std::vector<int>& a, int x) {
    // возвращает минимальное i такое, что a[i] >= x
    int l = -1;
    int r = a.size();  // l и r изначально указывают на фиктивные элементы
    
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (a[m] < x) {
            l = m;  // условие на l не нарушилось
        } else {
            r = m;  // условие на r не нарушилось
        }
    }
    return r;
}

int getLeftEntry(const std::vector<int>& a, int x) {
    // возвращает номер левого вхождения или -1
    int i = lowerBound(a, x);
    if (i == a.size() || 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$. Пример использования:

1
2
3
4
5
6
7
8

// минимальное i такое, что a[i] >= x; n, если все элементы а меньше х
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; -1, если все элементы а больше х
i = upper_bound(a, a + n, x) - a - 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 напишем цикл, делающий столько итераций, сколько нужно, чтобы условие точно выполнилось. Пример реализации:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def findRoot(L, R, eps):
    l, r = L, R
    k = int((r - l) / eps).bit_length()  # количество итераций для достижения точности eps
    
    for i in range(k):
        m = (l + r) / 2
        if f(m) < 0:
            l = m
        else:
            r = m
    return r

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <cmath>

double findRoot(double L, double R, double eps) {
    double l = L, r = R;
    
    // Количество итераций для достижения точности eps
    int k = static_cast<int>(log2((r - l) / eps)) + 1;
    
    for (int i = 0; i < k; i++) {
        double m = (l + r) / 2;
        if (f(m) < 0) {
            l = m;
        } else {
            r = m;
        }
    }
    return r;
}

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

# Исходные данные
a = [...]  # ваш массив
n = len(a)  # длина массива
M = ...  # ваше ограничение

maxLen = 0
ansL = 0
ansR = 0

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

print(f"maxLen = {maxLen}, ansL = {ansL}, ansR = {ansR}")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <vector>

int main() {
    // Исходные данные
    std::vector<int> a;  // ваш массив
    int n = a.size();    // длина массива
    int M;               // ваше ограничение
    
    // Пример инициализации (раскомментируйте при необходимости)
    // std::cin >> n >> M;
    // a.resize(n);
    // for (int i = 0; i < n; i++) std::cin >> a[i];
    
    int maxLen = 0;
    int ansL = 0;
    int ansR = 0;
    
    for (int l = 0; l < n; l++) {  // перебираем левую границу
        int sum = 0;  // будем считать сумму на текущем полуинтервале
        for (int r = l + 1; r <= n; r++) {
            sum += a[r - 1];
            if (sum <= M && r - l > maxLen) {
                maxLen = r - l;
                ansL = l;
                ansR = r;
            }
        }
    }
    
    std::cout << "maxLen = " << maxLen << ", ansL = " << ansL << ", ansR = " << ansR << std::endl;
    
    return 0;
}

Получилось решение за $\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]$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

a = [...]  # ваш массив
n = len(a)  # длина массива
M = ...  # ваше ограничение

maxLen = 0
ansL = 0
ansR = 0

# Предподсчитываем префиксные суммы
p = [0] * (n + 1)
for i in range(1, n + 1):
    p[i] = p[i - 1] + a[i - 1]

for l in range(n):
    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

# Результат: подмассив a[ansL:ansR] имеет максимальную длину с суммой <= M

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <vector>

// Входные данные
int n; // размер массива
std::vector<int> a(n); // исходный массив
int M; // ваше ограничение

int maxLen = 0, ansL = 0, ansR = 0;

// Предподсчитываем префиксные суммы
std::vector<int> p(n + 1);
p[0] = 0;
for (int i = 1; i <= n; i++) {
    p[i] = p[i - 1] + a[i - 1];
}

for (int l = 0; l < n; l++) {
    int sl = l;
    int sr = n + 1; // границы поиска, sum a[l..sl) <= M, sum a[l..sr) > M
    
    while (sr - sl > 1) {
        int 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;
    }
}

// Результат: подмассив a[ansL:ansR] имеет максимальную длину с суммой <= M

Перейдём теперь собственно к методу двух указателей. Пусть $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)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def find_max_subarray(a, M):
    n = len(a)
    maxLen = 0
    ansL = 0
    ansR = 0
    r = 0
    sum_ = 0
    
    for l in range(n):  # перебираем левую границу
        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]
    
    return ansL, ansR, maxLen

# Пример использования
a = [1, 2, 3, 4, 5]
M = 10
left, right, length = find_max_subarray(a, M)
print(f"Левая граница: {left}, Правая граница: {right}, Длина: {length}")
print(f"Подмассив: {a[left:right]}")

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
#include <vector>

void findMaxSubarray(const std::vector<int>& a, int M, int& ansL, int& ansR, int& maxLen) {
    int n = a.size();
    maxLen = 0;
    ansL = 0;
    ansR = 0;
    int r = 0;
    int sum = 0;
    
    for (int l = 0; l < n; l++) {  // перебираем левую границу
        while (r < n && sum + a[r] <= M) {
            sum += a[r];
            r++;
        }
        if (sum <= M && r - l > maxLen) {
            maxLen = r - l;
            ansL = l;
            ansR = r;
        }
        sum -= a[l];
    }
}

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    int M = 10;
    int left, right, length;
    
    findMaxSubarray(a, M, left, right, length);
    
    cout << "Левая граница: " << left << ", Правая граница: " << right << ", Длина: " << length << endl;
    cout << "Подмассив: ";
    for (int i = left; i < right; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    
    return 0;
}