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

Бінарний пошук — той алгоритм, який усі «знають», але майже ніхто не пише з першого разу без помилок на одиницю. Причина проста: його зазвичай вчать як рецепт: l, r, m, ділимо навпіл. Але насправді бінарний пошук треба розуміти через інваріант. А ще його майже ніколи не показують у тій формі, в якій він реально трапляється на роботі: не «знайти елемент у масиві», а «знайти мінімальне значення параметра, при якому система ще витримує навантаження». Розберемо обидва випадки.

1. Вгадай число

Загадано ціле число x від 1 до 100. Ви ставите питання, на які є відповідь «так» або «ні». За скільки питань у найгіршому випадку можна знайти x?

Стратегія: тримаємо відрізок кандидатів [l, r]. Спочатку це [1, 100]. На кожній ітерації беремо середину: m = ⌊(l + r) / 2⌋. Після цього питаємо: x > m? І відрізаємо половину варіантів.

l, r = 1, 100

while l < r:
    m = (l + r) // 2
    resp = input(f'x > {m}?')
    if resp == 'yes':
        l = m + 1
    else:
        r = m

print(f'x = {l}')

Для x = 42 це може виглядати так:

x > 50? no
x > 25? yes
x > 38? yes
x > 44? no
x > 41? yes
x > 43? no
x > 42? no
x = 42

Сім питань. Довжина відрізка гарантовано зменшується приблизно вдвічі, тому потрібно ceil(log₂ n) питань. Для n = 100 це: ceil(log₂ 100) = ceil(6.64) = 7

Зверніть увагу на дві деталі, які роблять цей цикл коректним.

Інваріант: відповідь завжди лежить у [l, r]. Жодне присвоєння цього не порушує.

Прогрес: l = m + 1 і r = m строго звужують відрізок. Якби ми написали l = m, цикл міг би зависнути у випадку l = r - 1. Це весь бінарний пошук. Далі — лише варіації.

2. У відсортованому масиві

Знайти x у невідсортованому масиві — це O(n). Іншого способу немає. Але у відсортованому масиві можна знайти нижню межу — lower_bound: найлівішу позицію, де елемент більший або дорівнює x. Після цього достатньо перевірити, чи цей елемент справді дорівнює x.

Ось тут більшість реалізацій і ламається. Формулюємо через інваріант напівінтервалу [l, r): l — межа, лівіше якої всі елементи строго менші за x.

r — межа, починаючи з якої всі елементи більші або дорівнюють x.

bool contains(const vector<int>& a, int x) {
    int l = 0, r = a.size();          // напівінтервал [l, r)

    while (l < r) {
        int m = l + (r - l) / 2;      // без переповнення

        if (a[m] < x)
            l = m + 1;                // a[m] точно не підходить
        else
            r = m;                    // a[m] ще може бути
    }

    return l < (int)a.size() && a[l] == x;
}

Коли цикл завершується, l == r. Це і є позиція lower_bound. Якщо x більший за всі елементи, тоді l == a.size(), тому перевірка меж у return обов’язкова.

Дві типові помилки, які можуть коштувати годину дебагу:

int m = (l + r) / 2;

Цей варіант може переповнитися при великих l і r. Краще писати так:

int m = l + (r - l) / 2;

Друга помилка — асиметричні присвоєння l = m / r = m в одному циклі. Одна з гілок мусить зсуватися на одиницю, інакше цикл може не завершитися. Яка саме — визначається інваріантом, а не інтуїцією.

У C++ це вже є в стандартній бібліотеці:

bool contains(const vector<int>& a, int x) {
    auto it = lower_bound(a.begin(), a.end(), x);
    return it != a.end() && *it == x;
}

upper_bound знаходить перший елемент, який строго більший за аргумент.

Різниця: upper_bound - lower_bound дає кількість входжень x. У Python для цього є bisect.bisect_left і bisect.bisect_right. Коли це справді дає виграш? Бінарний пошук по масиву сам по собі не дуже корисний: щоб побудувати масив розміру n, ви вже витратили O(n). Виграш з’являється тоді, коли структура будується один раз, а запитів багато. Наприклад, m запитів можна обробити за: O(n log n + m log n) замість: O(nm)

3. Насправді ми шукаємо не елемент, а межу монотонності

Узагальнимо. Є предикат f(x), який на всій області визначення спочатку хибний, а потім істинний. Або навпаки.

Наприклад:

f: 0 0 0 0 0 1 1 1 1 1

Бінарний пошук знаходить точку переходу. Пошук lower_bound — це окремий випадок, де:

f(k) = a[k] >= x

Інші задачі, які зводяться до того самого циклу:

• знайти останнє входження x у відсортованому масиві;

• порахувати, скільки разів x зустрічається;

• у масиві, де спочатку йдуть непарні числа, а потім парні, знайти індекс, з якого починаються парні.

Єдина вимога — монотонність предиката. Не «масив відсортований», а саме монотонність f. Це критично для наступного розділу.

4. Дійсні аргументи

Тепер аргумент — не індекс, а дійсне число.

Класичний приклад: обчислити √2, тобто знайти точку переходу предиката:

f(x) = x² >= 2

Проблема в тому, що дійсні числа в комп’ютері зберігаються неточно:

>>> 0.1 + 0.1 + 0.1
0.30000000000000004

Точне значення √2 ми не отримаємо ніколи — це нескінченний неперіодичний дріб.

Тому важливо:

1. Переконатися, що на старті f(l) хибний, а f(r) істинний. Це не автоматично.

2. Не зупинятися за умови r - l < eps. Краще робити фіксовану кількість ітерацій. Так, цикл завжди завершиться, а асимптотика буде передбачуваною.

Скільки ітерацій потрібно? Один десятковий розряд коштує приблизно три кроки бінарного пошуку, бо:

log₂ 10 ≈ 3.32

Для шести знаків після коми потрібно близько 20 кроків після того, як відрізок стиснувся до одиниці. Сто ітерацій вистачає із запасом для будь-яких розумних цілей.

double sqrt_bs(double x) {
    double l = 0, r = max(x, 1.0);   // ключовий момент

    for (int i = 0; i < 100; i++) {
        double m = (l + r) / 2;

        if (m * m < x)
            l = m;
        else
            r = m;
    }

    return l;
}

Чому max(x, 1.0), а не просто x? Бо для x < 1 виконується:

√x > x

Тобто відповідь опиняється за межами початкового відрізка. Інваріант «відповідь у [l, r]» порушено ще до першої ітерації, і бінарний пошук чесно повертає неправильний результат.

Це найпоширеніший баг у бінарному пошуку по дійсних числах. Його не видно на тестах, де x > 1. Той самий цикл знаходить нуль будь-якої неперервної функції, для якої відомі точки різних знаків.

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

Тепер головне. Часто задача звучить так, що прямого алгоритму не видно.

Наприклад: «Корови в стійлах».

На прямій розташовані n стійл, заданих координатами. Треба розставити k корів так, щоб мінімальна відстань між будь-якими двома коровами була якомога більшою. Гарантовано, що: 1 < k < n

Це оптимізаційна задача. У лоб не зовсім зрозуміло, з чого почати. Прийом такий: замінити «знайти оптимум» на «перевірити, чи досяжне значення x».

Ці дві задачі не еквівалентні за складністю. Друга часто набагато простіша.

Припустимо, ми зафіксували x — мінімальну допустиму відстань. Чи вдасться розставити k корів?

Робимо жадібно: перша корова йде в найлівіше стійло. Це завжди не гірше за будь-яку альтернативу. Далі йдемо зліва направо і ставимо корову в перше стійло, яке віддалене від попередньої корови не менше ніж на x.

bool check(int x) {
    int cows = 1;
    int last_cow = coords[0];

    for (int i = 1; i < coords.size(); i++) {
        if (coords[i] - last_cow >= x) {
            cows++;
            last_cow = coords[i];
        }
    }

    return cows >= k;
}

Якщо вдалося жадібно розставити хоча б k корів, тоді відповідь не менша за x.

Якщо не вдалося — відповідь строго менша за x. І ось воно: check(x) монотонний. Для малих x він істинний. Для великих — хибний. Отже, є точка переходу. А точки переходу ми вже вміємо знаходити.

int solve() {
    sort(coords.begin(), coords.end());
    int l = 0;                              
    int r = coords.back() - coords[0] + 1; 
    while (r - l > 1) {
        int m = l + (r - l) / 2;

        if (check(m))
            l = m;                          // l завжди досяжний
        else
            r = m;                          // r завжди недосяжний
    }

    return l;
}

Інваріант:

check(l) == true
check(r) == false

На виході:

r == l + 1

Тобто l — максимальний досяжний x. Кожна перевірка працює за O(n). Зовнішній бінарний пошук робить O(log X) ітерацій, де X — діапазон координат.

Разом отримуємо:

O(n log n + n log X)

Що з цього забрати

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

Чекліст, коли задача пахне бінарним пошуком по відповіді:

1. У формулюванні є «мінімізувати максимум» або «максимізувати мінімум». Майже завжди це натяк.

2. Ви можете написати check(x), яка відповідає на питання «чи досяжне x?» простіше, ніж розв’язати початкову задачу. Зазвичай це жадібний алгоритм або лінійний прохід.

3. check(x) монотонний. Це треба довести, а не відчути. Якщо x досяжне, то будь-яке менше x' < x теж досяжне — ось це і є потрібне твердження.

І три речі, які варто перевіряти в кожній реалізації:

1. Інваріант існує і сформульований словами. Не просто «l — ліва межа», а, наприклад: check(l) істинний, check(r) хибний.

2. Початкові межі задовольняють інваріант.

3. Цикл завершується. Одна гілка зсувається на одиницю, або кількість ітерацій фіксована.

Той самий шаблон ви пишете, коли підбираєте максимальний розмір батча, за якого p99-латентність ще вкладається в SLA, або мінімальну кількість реплік, за якої система переживає пік. check() — це навантажувальний тест. Монотонність — це припущення про поведінку системи. А помилка на одиницю — це потенційний інцидент.