Перейти до основного вмісту

Бінарний пошук

Бінарний пошук — це метод, який дозволяє швидше шукати щось шляхом розбиття інтервалу пошуку на дві частини. Найпоширеніше його застосування — пошук значень у відсортованих масивах, однак сама ідея розбиття є ключовою в багатьох інших типових задачах.

Коли підходить цей алгоритм?
  • Масив відсортований або предикат монотонний («якщо xx підходить, то і все більше за xx підходить»)? (якщо ні, а функція унімодальна — спершу зростає, потім спадає → Тернарний пошук)
  • Шукаєте конкретне значення / точку переходу, а не максимум чи мінімум функції?
  • Корінь гладкої функції з відомою похідною, де потрібна швидка квадратична збіжність? (якщо так → Метод Ньютона)

Пошук у відсортованих масивах​

Найтиповіша задача, яка приводить до бінарного пошуку, виглядає так. Вам дано відсортований масив A0≤A1≤⋯≤An−1A_0 \leq A_1 \leq \dots \leq A_{n-1}, перевірте, чи присутнє kk у цій послідовності. Найпростіший розв'язок — перевіряти кожен елемент по черзі й порівнювати його з kk (так званий лінійний пошук). Цей підхід працює за O(n)O(n), але не використовує того факту, що масив відсортований.


Бінарний пошук значення 77 у масиві.
Зображення від AlwaysAngry поширюється за ліцензією CC BY-SA 4.0.

Тепер припустимо, що ми знаємо два індекси L<RL < R такі, що AL≤k≤ARA_L \leq k \leq A_R. Оскільки масив відсортований, ми можемо зробити висновок, що kk або зустрічається серед AL,AL+1,…,ARA_L, A_{L+1}, \dots, A_R, або не зустрічається в масиві взагалі. Якщо ми оберемо довільний індекс MM такий, що L<M<RL < M < R, і перевіримо, чи kk менше за AMA_M, чи більше. Маємо два можливі випадки:

  1. AL≤k≤AMA_L \leq k \leq A_M. У цьому випадку ми зводимо задачу з [L,R][L, R] до [L,M][L, M];
  2. AM≤k≤ARA_M \leq k \leq A_R. У цьому випадку ми зводимо задачу з [L,R][L, R] до [M,R][M, R].

Коли неможливо обрати MM, тобто коли R=L+1R = L + 1, ми безпосередньо порівнюємо kk з ALA_L і ARA_R. Інакше ми хотіли б обрати MM так, щоб якнайшвидше звести активний відрізок до одного елемента в найгіршому випадку.

Оскільки в найгіршому випадку ми завжди зводитимемо до більшого з відрізків [L,M][L, M] і [M,R][M, R]. Отже, у найгіршому сценарії зведення відбуватиметься від R−LR-L до max⁡(M−L,R−M)\max(M-L, R-M). Щоб мінімізувати це значення, ми маємо обрати M≈L+R2M \approx \frac{L+R}{2}, тоді

M−L≈R−L2≈R−M.M-L \approx \frac{R-L}{2} \approx R-M.

Іншими словами, з точки зору найгіршого випадку оптимально завжди обирати MM посередині [L,R][L, R] і ділити його навпіл. Отже, активний відрізок зменшується вдвічі на кожному кроці, доки не стане розміром 11. Тож, якщо процес потребує hh кроків, то наприкінці він зменшує різницю між RR і LL з R−LR-L до R−L2h≈1\frac{R-L}{2^h} \approx 1, що дає нам рівняння 2h≈R−L2^h \approx R-L.

Узявши log⁡2\log_2 від обох частин, отримуємо h≈log⁡2(R−L)∈O(log⁡n)h \approx \log_2(R-L) \in O(\log n).

Логарифмічна кількість кроків разюче краща, ніж у лінійного пошуку. Наприклад, для n≈220≈106n \approx 2^{20} \approx 10^6 для лінійного пошуку вам знадобилося б приблизно мільйон операцій, але лише близько 2020 операцій з бінарним пошуком.

Нижня та верхня межі​

Часто зручніше знайти позицію першого елемента, який більший або рівний за kk (так звана нижня межа kk у масиві), або позицію першого елемента, який більший за kk (так звана верхня межа kk), ніж точну позицію елемента.

Разом нижня та верхня межі утворюють (можливо, порожній) напівінтервал елементів масиву, які дорівнюють kk. Щоб перевірити, чи присутнє kk у масиві, достатньо знайти його нижню межу й перевірити, чи відповідний елемент дорівнює kk.

Реалізація​

Пояснення вище дає приблизний опис алгоритму. Для деталей реалізації нам потрібно бути точнішими.

Ми підтримуватимемо пару L<RL < R таку, що AL≤k<ARA_L \leq k < A_R. Це означає, що активний інтервал пошуку — це [L,R)[L, R). Ми використовуємо тут напівінтервал замість відрізка [L,R][L, R], бо це, як виявляється, потребує менше роботи з крайовими випадками.

Коли R=L+1R = L+1, з наведених вище означень ми можемо зробити висновок, що RR — це верхня межа kk. Зручно ініціалізувати RR індексом за межею масиву, тобто R=nR=n, а LL — індексом перед початком масиву, тобто L=−1L=-1. Це нормально, доки ми ніколи не обчислюємо ALA_L і ARA_R безпосередньо в нашому алгоритмі, формально вважаючи їх AL=−∞A_L = -\infty і AR=+∞A_R = +\infty.

Нарешті, щоб конкретизувати значення MM, яке ми обираємо, ми зупинимося на M=⌊L+R2⌋M = \lfloor \frac{L+R}{2} \rfloor.

Тоді реалізація могла б виглядати так:

... // відсортований масив зберігається як a[0], a[1], ..., a[n-1]
int l = -1, r = n;
while (r - l > 1) {
    int m = (l + r) / 2;
    if (k < a[m]) {
        r = m; // a[l] <= k < a[m] <= a[r]
    } else {
        l = m; // a[l] <= a[m] <= k < a[r]
    }
}

Під час виконання алгоритму ми ніколи не обчислюємо ні ALA_L, ні ARA_R, оскільки L<M<RL < M < R. Наприкінці LL буде індексом останнього елемента, який не більший за kk (або −1-1, якщо такого елемента немає), а RR буде індексом першого елемента, більшого за kk (або nn, якщо такого елемента немає).

Зауваження. Обчислення m як m = (r + l) / 2 може призвести до переповнення, якщо l і r — два додатні цілі числа, і ця помилка прожила близько 9 років у JDK, як описано в блогпості. Деякі альтернативні підходи включають, наприклад, запис m = l + (r - l) / 2, який завжди працює для додатних цілих l і r, але все одно може переповнитися, якщо l — від'ємне число. Якщо ви використовуєте C++20, він пропонує альтернативне рішення у вигляді m = std::midpoint(l, r), яке завжди працює коректно.

Пошук за довільним предикатом​

Нехай f:{0,1,…,n−1}→{0,1}f : \{0,1,\dots, n-1\} \to \{0, 1\} — булева функція, визначена на 0,1,…,n−10,1,\dots,n-1 так, що вона монотонно зростає, тобто

f(0)≤f(1)≤⋯≤f(n−1).f(0) \leq f(1) \leq \dots \leq f(n-1).

Бінарний пошук у тому вигляді, як його описано вище, знаходить розбиття масиву за предикатом f(M)f(M), що містить булеве значення виразу k<AMk < A_M. Замість k<AMk < A_M можна використати довільний монотонний предикат. Це особливо корисно, коли обчислення f(k)f(k) потребує надто багато часу, щоб насправді обчислювати його для кожного можливого значення. Іншими словами, бінарний пошук знаходить єдиний індекс LL такий, що f(L)=0f(L) = 0 і f(R)=f(L+1)=1f(R)=f(L+1)=1, якщо така точка переходу існує, або дає нам L=n−1L = n-1, якщо f(0)=⋯=f(n−1)=0f(0) = \dots = f(n-1) = 0, або L=−1L = -1, якщо f(0)=⋯=f(n−1)=1f(0) = \dots = f(n-1) = 1.

Доведення коректності за припущення, що точка переходу існує, тобто f(0)=0f(0)=0 і f(n−1)=1f(n-1)=1: реалізація підтримує інваріант циклу f(l)=0,f(r)=1f(l)=0, f(r)=1. Коли r−l>1r - l > 1, вибір mm означає, що r−lr-l завжди зменшуватиметься. Цикл завершується, коли r−l=1r - l = 1, що дає нам бажану точку переходу.

... // f(i) — це булева функція така, що f(0) <= ... <= f(n-1)
int l = -1, r = n;
while (r - l > 1) {
    int m = (l + r) / 2;
    if (f(m)) {
        r = m; // 0 = f(l) < f(m) = 1
    } else {
        l = m; // 0 = f(m) < f(r) = 1
    }
}

Бінарний пошук по відповіді​

Така ситуація часто виникає, коли нас просять обчислити деяке значення, але ми здатні лише перевірити, чи це значення не менше за ii. Наприклад, вам дано масив a1,…,ana_1,\dots,a_n і просять знайти максимальну заокруглену вниз середню суму

⌊al+al+1+⋯+arr−l+1⌋\left \lfloor \frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \right\rfloor

серед усіх можливих пар l,rl,r таких, що r−l≥xr-l \geq x. Один із простих способів розв'язати цю задачу — перевіряти, чи відповідь не менша за λ\lambda, тобто чи існує пара l,rl, r така, що виконується наступне:

al+al+1+⋯+arr−l+1≥λ.\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1} \geq \lambda.

Еквівалентно це переписується як

(al−λ)+(al+1−λ)+⋯+(ar−λ)≥0,(a_l - \lambda) + (a_{l+1} - \lambda) + \dots + (a_r - \lambda) \geq 0,

тож тепер нам потрібно перевірити, чи існує підмасив нового масиву ai−λa_i - \lambda довжиною щонайменше x+1x+1 з невід'ємною сумою, що можна зробити за допомогою префіксних сум.

Нехай f:R→Rf : \mathbb R \to \mathbb R — дійснозначна функція, неперервна на відрізку [L,R][L, R].

Без втрати загальності припустимо, що f(L)≤f(R)f(L) \leq f(R). З теореми про проміжне значення випливає, що для будь-якого y∈[f(L),f(R)]y \in [f(L), f(R)] існує x∈[L,R]x \in [L, R] таке, що f(x)=yf(x) = y. Зауважимо, що, на відміну від попередніх параграфів, тут від функції не вимагається монотонності.

Значення xx можна наблизити з точністю до ±δ\pm\delta за час O(log⁡R−Lδ)O\left(\log \frac{R-L}{\delta}\right) для будь-якого конкретного значення δ\delta. Ідея, по суті, та сама: якщо ми візьмемо M∈(L,R)M \in (L, R), то зможемо звести інтервал пошуку або до [L,M][L, M], або до [M,R][M, R] залежно від того, чи f(M)f(M) більше за yy. Одним поширеним прикладом тут було б знаходження коренів многочленів непарного степеня.

Наприклад, нехай f(x)=x3+ax2+bx+cf(x)=x^3 + ax^2 + bx + c. Тоді f(L)→−∞f(L) \to -\infty і f(R)→+∞f(R) \to +\infty при L→−∞L \to -\infty і R→+∞R \to +\infty. Це означає, що завжди можна знайти достатньо мале LL і достатньо велике RR такі, що f(L)<0f(L) < 0 і f(R)>0f(R) > 0. Тоді за допомогою бінарного пошуку можна знайти як завгодно малий інтервал, що містить xx таке, що f(x)=0f(x)=0.

Пошук зі степенями двійки​

Ще один вартий уваги спосіб виконувати бінарний пошук — це, замість підтримки активного відрізка, підтримувати поточний вказівник ii і поточний степінь kk. Вказівник починається з i=Li=L, а потім на кожній ітерації тестується предикат у точці i+2ki+2^k. Якщо предикат досі 00, вказівник просувається з ii до i+2ki+2^k, інакше він залишається тим самим, після чого степінь kk зменшується на 11.

Ця парадигма широко використовується в задачах про дерева, таких як знаходження найнижчого спільного предка двох вершин або знаходження предка конкретної вершини, який має певну висоту. Її також можна адаптувати, наприклад, для знаходження kk-го ненульового елемента в дереві Фенвіка.

Задачі для практики​

Відеоматеріали​