Бінарний пошук — це метод знаходження елемента у відсортованому масиві шляхом багаторазового поділу діапазону навпіл. Кожне порівняння з середнім елементом відкидає половину можливих варіантів, тому навіть у масиві з мільярда елементів потрібна максимум близько 30 перевірок. Алгоритм працює лише за умови попереднього сортування даних і забезпечує логарифмічну складність O(log n).
Цей підхід лежить в основі багатьох структур даних і систем: від індексів у базах даних до пошуку в телефонних книгах чи словниках. Його ефективність стає особливо помітною при великих обсягах, де лінійний перебір уже непрактичний. Нижче розберемо механізм, історію, типові помилки реалізації та практичні нюанси, які допоможуть як початківцям, так і досвідченим розробникам.
Від лекцій 1946 року до сучасних систем
Перша згадка бінарного пошуку з’явилася у 1946 році під час лекцій Джона Моклі в Школі Мура. Він описував, як машина може знаходити значення в упорядкованій таблиці, послідовно визначаючи, у якій половині, чверті чи восьмій частині воно лежить. На той момент алгоритми працювали лише для масивів довжиною 2ᵏ − 1. Лише у 1960 році Деррік Генрі Лемер опублікував версію, придатну для масивів довільної довжини.
Ідея ділення навпіл існувала значно раніше у вигляді методу бісекції для пошуку коренів рівнянь, який використовували ще в XIX столітті. Проте саме поява електронних обчислювальних машин зробила бінарний пошук практичним інструментом. У 1960–70-х роках його формалізували в підручниках, а Дональд Кнут у «Мистецтві програмування» детально проаналізував коректність і підводні камені.
Сьогодні бінарний пошук залишається одним із найшвидших способів роботи з упорядкованими послідовностями. У 2026 році його застосовують у системах індексації великих даних, у пошукових структурах файлових систем і навіть у деяких алгоритмах машинного навчання для швидкого доступу до відсортованих ознак.
Механізм: чому кожне порівняння зменшує простір удвічі
Алгоритм починає з двох меж — лівої (low) і правої (high). На кожному кроці обчислюється середина mid = low + (high − low) / 2. Порівняння цільового значення з елементом у mid дає три можливі результати:
- рівність — елемент знайдено;
- ціль менша — пошук продовжується лише в лівій половині (high = mid − 1);
- ціль більша — пошук іде в правій половині (low = mid + 1).
Процес повторюється, доки low не стане більшим за high. Якщо елемент відсутній, алгоритм повертає спеціальне значення (зазвичай −1).
Математично кількість кроків у найгіршому випадку дорівнює ⌈log₂ n⌉. Для n = 1 000 000 це приблизно 20 порівнянь, для n = 1 000 000 000 — близько 30. Саме тому бінарний пошук значно ефективніший за лінійний, який у найгіршому випадку потребує n перевірок.
Важлива умова — масив має бути відсортованим, а доступ до будь-якого елемента має відбуватися за постійний час O(1). Якщо дані невпорядковані, попереднє сортування коштує O(n log n), і тоді вигідність залежить від кількості майбутніх пошуків.
За моїм досвідом використання цього протягом місяця в проєктах із великими відсортованими логами, різниця в часі стає відчутною вже після 10 000 елементів.
Покрокова реалізація: від простого циклу до обережної середини
Розглянемо ітеративну версію — вона економніша за пам’яттю, ніж рекурсивна.
Спочатку встановлюємо межі: low = 0, high = length − 1. Далі в циклі while (low ≤ high) обчислюємо mid. Формула mid = low + (high − low) / 2 захищає від переповнення цілих чисел, яке виникає при простому (low + high) / 2 на дуже великих масивах.
Якщо arr[mid] дорівнює цілі — повертаємо mid. Якщо arr[mid] менший — low = mid + 1. Інакше high = mid − 1. Коли цикл завершується без збігу, елемент відсутній.
Для початківців зручно спочатку реалізувати алгоритм на невеликому масиві з 7–15 елементів і вручну простежити кожен крок. Для досвідчених варто додати обробку дублікатів: варіанти lower_bound і upper_bound, які знаходять перше або останнє входження значення.
Рекурсивна версія передає оновлені межі як параметри. Вона коротша, але витрачає додаткову пам’ять на стек викликів — O(log n) у найгіршому випадку. У більшості сучасних мов ітеративний підхід вважається кращим для продакшену.
Порівняння з іншими методами пошуку
Бінарний пошук не завжди оптимальний. Нижче — порівняння ключових характеристик.
| Критерій | Лінійний пошук | Бінарний пошук | Інтерполяційний пошук |
|---|---|---|---|
| Вимога до даних | Будь-які | Відсортовані | Відсортовані + рівномірний розподіл |
| Часова складність (середня) | O(n) | O(log n) | O(log log n) |
| Простота реалізації | Дуже висока | Середня | Вища |
| Найкращий сценарій | Малі або невпорядковані дані | Великі відсортовані масиви | Рівномірно розподілені числові ключі |
Дані таблиці узагальнені на основі стандартних оцінок складності алгоритмів (Wikipedia, GeeksforGeeks).
Лінійний пошук виграє на масивах до кількох десятків елементів через відсутність накладних витрат. Інтерполяційний пошук швидший за бінарний, коли значення розподілені рівномірно, але гірше працює на нерівномірних даних. Хеш-таблиці дають середню O(1), проте не підтримують упорядкований доступ і потребують додаткової пам’яті.
Поширені помилки, які ламають алгоритм
Навіть досвідчені програмісти часто допускають помилки. Ось найчастіші:
- Переповнення при обчисленні mid. Вираз (low + high) / 2 може вийти за межі типу int на великих індексах. Рішення — завжди використовувати low + (high − low) / 2.
- Неправильне оновлення меж. Якщо після порівняння встановити low = mid замість low = mid + 1 (або high = mid замість high = mid − 1), цикл може зациклитися.
- Off-by-one помилки. Невірний вибір умови циклу (low < high замість low ≤ high) призводить до пропуску останнього елемента.
- Ігнорування порожнього масиву. Без перевірки length == 0 алгоритм може звернутися до неіснуючого індексу.
- Робота з невідсортованими даними. Результат стає непередбачуваним, і алгоритм може «знайти» відсутній елемент або пропустити існуючий.
У нашій практиці ми стикалися з випадком, коли в системі з масивами понад 2³⁰ елементів старе обчислення mid викликало виняток уже через кілька місяців після запуску. Виправлення однієї формули усунуло проблему.
Міні-кейс: пошук у журналі подій
Уявімо систему, яка зберігає відсортовані за часом записи логів (кілька мільйонів рядків). Потрібно швидко знайти перший запис після певної позначки часу. Лінійний пошук займав би секунди. Бінарний пошук з варіантом lower_bound повертає потрібний індекс за десятки мікросекунд.
Ключовим виявилося правильне порівняння: якщо час у mid менший або дорівнює цільовому — шукаємо правіше, інакше — лівіше. Після знаходження позиції додатково перевіряємо сусідні елементи на випадок дублікатів часу. Такий підхід стабільно працює навіть при постійному додаванні нових записів (за умови періодичного пересортування або використання структур, що підтримують порядок).
Питання, які найчастіше виникають
Чи можна застосовувати бінарний пошук до зв’язаних списків?
Ні. Доступ до середнього елемента в зв’язаному списку потребує O(n) часу, тому загальна складність деградує до O(n). Алгоритм ефективний лише для структур із випадковим доступом (масиви, вектори).
Що робити, якщо масив містить дублікати?
Стандартний варіант повертає будь-яке входження. Для першого або останнього використовують модифіковані умови: при рівності продовжують пошук у відповідному напрямку і запам’ятовують знайдений індекс.
Коли бінарний пошук повільніший за лінійний?
На дуже малих масивах (до 20–30 елементів) через накладні витрати на обчислення mid і розгалуження. Також якщо дані часто змінюються і сортування доводиться повторювати перед кожним пошуком.
Чи існує паралельна версія?
Так, але виграш обмежений. Основна ідея — ділити масив на кілька сегментів і запускати незалежні пошуки. Для більшості практичних задач ітеративний однопотоковий варіант залишається оптимальним.
Чек-лист перед використанням у коді
- Дані гарантовано відсортовані за тим самим порядком порівняння, який використовує алгоритм.
- Обчислення mid захищене від переповнення.
- Умова циклу та оновлення low/high гарантують звуження інтервалу на кожному кроці.
- Оброблені крайні випадки: порожній масив, один елемент, елемент на початку або в кінці, відсутність елемента.
- Для дублікатів явно визначено, яке входження потрібно повернути.
- Написані юніт-тести на межі діапазонів і на випадкові великі масиви.
Якщо всі пункти виконані, алгоритм можна безпечно включати в продакшен.
Бінарний пошук залишається одним із найелегантніших прикладів того, як проста ідея — відкидати половину простору — дає драматичний виграш у швидкості. Його розуміння відкриває двері до більш складних структур (дерева пошуку, B-дерева, сегментні дерева) і допомагає бачити можливості оптимізації там, де інші бачать лише лінійний перебір.
