1. Навіщо потрібен бінарний пошук
Коли ви тільки починаєте програмувати, пошук зазвичай виглядає так: «пройдемося масивом і порівняємо кожен елемент». І це цілком нормально — так роблять усі, зокрема й досвідчені розробники, якщо масив невеликий. Але в цього підходу є неприємна особливість: що більше даних, то більше часу ви витрачаєте на просте «подивитися». Бінарний пошук — це спосіб шукати у відсортованому масиві, щоразу відкидаючи половину варіантів.
Уявіть, що ви шукаєте книгу в бібліотеці. Можна йти полицями зліва направо, перевіряючи кожну книгу — це лінійний пошук. А можна скористатися тим, що книги відсортовані: подивилися на середину, зрозуміли, що потрібна книга далі, відсікли половину бібліотеки, повторили. Бінарний пошук — це ніби «внутрішній бібліотекар», тільки без осудливого погляду.
Порівняймо підходи в невеликій таблиці:
| Підхід | Вимога до даних | Скільки порівнянь (приблизно) | Складність |
|---|---|---|---|
| Лінійний пошук | нічого | до n | |
| Бінарний пошук | масив відсортовано | до log2(n) | |
Ідея O(log n) тут дуже проста: діапазон пошуку на кожному кроці зменшується приблизно вдвічі. Було 100 елементів — стало 50 — 25 — 12 — 6 — 3 — 1. Тобто ви не обходите дані, а поступово звужуєте коридор.
2. Передумова: масив відсортовано
Дуже хочеться одразу написати бінарний пошук і запускати його всюди, бо він звучить як безкоштовне прискорення. Але в алгоритмів є характер: бінарний пошук не працює в хаосі. Йому потрібен порядок. Причому не просто «якось відсортовано», а відсортовано за тим самим правилом порівняння, яке ви використовуєте всередині пошуку. Це важливіше, ніж здається: сортування рядків і сортування чисел — різні світи.
Якщо ви відсортували рядки як рядки, то "10" буде «меншим» за "2" — лексикографічно. І бінарний пошук чесно дотримуватиметься цього правила. Просто результат може здивувати людину, яка очікувала числового порядку.
Для нашої навчальної історії візьмемо масив bookIDs — ідентифікатори книг — як Int, тому що числа сортуються «по-людськи»: 1, 2, 10, 50.
Підготовка даних:
import Foundation
var bookIDs = [42, 7, 100, 15, 7]
bookIDs.sort()
print(bookIDs) // [7, 7, 15, 42, 100]
Зверніть увагу: дублікати (7) нікуди не поділися. Сортування не видаляє елементи, а лише змінює їхній порядок.
3. Межі та інваріант
Бінарний пошук зазвичай ламається не через складну математику, а через дрібні помилки в межах. Тому перед кодом нам потрібно вибрати й зафіксувати правила гри: які індекси ми вважаємо в діапазоні пошуку, як обчислюємо середину і що саме змінюємо після порівняння. Це називається «тримати інваріант» — розумне слово, а простіше кажучи, не брехати самому собі у змінних.
Включний діапазон left...right
Ми виберемо найзрозуміліший для новачка варіант: left і right — це індекси включного діапазону, тобто обидва кінці входять. Тоді умова циклу буде left <= right. Якщо стало left > right, значить діапазон порожній, і елемента немає.
Схема діапазону:
індекси: 0 1 2 3 4
масив: [7, 15, 42, 100, 120]
left = 0
right = 4 (останній допустимий індекс)
Саме тому right зазвичай дорівнює array.count - 1, а не array.count. Якщо поставити count, то ви одразу отримаєте ризик виходу за межі, а Swift цього не пробачає.
Середина та відкидання половини
Тепер давайте зберемо ідею так, щоб код був майже очевидним. Ми беремо середину діапазону, порівнюємо значення посередині з тим, що шукаємо, і вирішуємо, де продовжити. Якщо значення дорівнює — перемога. Якщо менше — шукане праворуч. Якщо більше — ліворуч. І дуже важливо: після порівняння ми маємо переступити через середину, інакше можемо зациклитися.
Ось чому зазвичай пишуть left = mid + 1 або right = mid - 1. Якщо зробити left = mid, то mid може не змінюватися, і цикл стане вічним. А вічні цикли — це як вічні ремонти: теоретично можливі, але краще без них.
Невелика блок-схема — псевдологіка, але вона добре запам’ятовується:
flowchart TD
A[Початок: left=0, right=count-1] --> B{left <= right?}
B -- ні --> Z[Повернути nil]
B -- так --> C["mid = left + (right-left)/2"]
C --> D{"array[mid] == target?"}
D -- так --> E[Повернути mid]
D -- ні --> F{"array[mid] < target?"}
F -- так --> G[left = mid + 1]
F -- ні --> H[right = mid - 1]
G --> B
H --> B
Формула left + (right - left) / 2 виглядає трохи занудно, але вона допомагає уникнути деяких помилок в обчисленнях і візуально підкреслює: середина завжди всередині поточного діапазону.
4. Ітеративна реалізація
Функція binarySearch
Тепер найприємніше — написати функцію, яка повертає Int?. Чому Optional? Тому що чесна відповідь «не знайдено» — це nil. Повернути -1 теж можна, але це вже окрема домовленість, а вона часто призводить до помилок. Наприклад, хтось забуде перевірити -1 і піде за індексом.
Зробимо версію для [Int]. Ми не використовуємо дженерики, тому що це буде пізніше в курсі. Зараз нам важливіше, щоб код був простий і читабельний.
import Foundation
func binarySearch(_ array: [Int], target: Int) -> Int? { // Повертає індекс target або nil
guard !array.isEmpty else { return nil } // Якщо масив порожній, шукати нічого
var left = 0 // Ліва межа діапазону пошуку
var right = array.count - 1 // Права межа діапазону пошуку
while left <= right { // Поки межі не перетнулися
let mid = left + (right - left) / 2 // Середина діапазону без ризику переповнення
let value = array[mid] // Значення елемента посередині
if value == target { return mid } // Знайшли елемент — повертаємо індекс
if value < target { left = mid + 1 } // Шукане значення праворуч
else { right = mid - 1 } // Шукане значення ліворуч
}
return nil // Якщо цикл завершився, елемент не знайдено
}
Так, це більше ніж 10 рядків — але тут кожен рядок несе одну думку, і для алгоритму це важливіше, ніж штучно стискати код.
Трасування для налагодження
Дуже корисно вміти зазирнути всередину алгоритму: які left, right, mid він обирає. Це особливо рятує, коли щось не знаходиться, хоча «точно має бути».
Зробимо навчальну версію, яка друкує кроки. У реальному коді ви б це прибрали, але на етапі навчання це майже суперсила.
import Foundation
func binarySearchDebug(_ array: [Int], target: Int) -> Int? {
var left = 0, right = array.count - 1
while left <= right {
let mid = left + (right - left) / 2
print("L=\(left) R=\(right) mid=\(mid) val=\(array[mid])")
if array[mid] == target { return mid }
if array[mid] < target { left = mid + 1 } else { right = mid - 1 }
}
return nil
}
Приклад запуску:
import Foundation
let sorted = [7, 7, 15, 42, 100]
let idx = binarySearchDebug(sorted, target: 42)
print(idx as Any) // Optional(3)
Ви побачите звуження коридору просто в консолі. І якщо у вас раптом left та right перестали рухатися, значить, ви десь не переступили через mid.
5. Використовуємо в невеликому застосунку
Щоб приклади не були набором розрізнених фрагментів, уявімо, що ми пишемо невеликий консольний застосунок «MiniLibrary»: у нас є список bookIDs, ми сортуємо його та швидко шукаємо потрібну книгу. Жодного повноцінного CLI та розбору команд — це буде значно пізніше; зараз ми розвиваємо навички алгоритмів.
Почнемо з підготовки даних і пошуку:
import Foundation
var bookIDs = [42, 7, 100, 15, 7]
bookIDs.sort()
let targetID = 15
let index = binarySearch(bookIDs, target: targetID)
print(index as Any) // Optional(2)
А тепер — акуратний вивід для людини. Оскільки index — Optional, скористаємося if let (ви вже це вмієте):
import Foundation
if let i = binarySearch(bookIDs, target: targetID) {
print("Книга з ID=\(targetID) на позиції \(i)") // Книга з ID=15 на позиції 2
} else {
print("Книги з ID=\(targetID) немає")
}
Зверніть увагу: «позиція» — це індекс у масиві, а не «номер книги в світі». Це вічна плутанина новачків: індекс — це координата в конкретному масиві.
Якщо не знайшли: nil проти «магічних чисел»
У бінарному пошуку «не знайдено» — абсолютно нормальний результат. Це не помилка програми, а звичайна ситуація. Саме тому повертати nil дуже зручно: ви не сплутаєте 0 — перший елемент — з «не знайдено».
Перевіримо сценарій, коли книги немає:
import Foundation
let sorted = [7, 7, 15, 42, 100]
let missing = binarySearch(sorted, target: 999)
print(missing as Any) // nil
І, якщо хочеться, можна дати значення за замовчуванням через ?? — наприклад, для виводу. Але пам’ятайте: ?? добре підходить для повідомлень, а не для логіки. Якщо ви підставите «-1» і забудете перевірити це значення, буде біда.
import Foundation
let idx = binarySearch(sorted, target: 999) ?? -1
print(idx) // -1
6. Коли бінарний пошук виправданий
Бінарний пошук крутий, але він не завжди кращий. Його суперсила зʼявляється, коли масив уже відсортовано або коли ви плануєте виконувати багато пошуків в одному й тому самому масиві. Якщо вам потрібно один раз знайти елемент у маленькому масиві з 10 штук, лінійний пошук простіший і часто швидший на практиці — через меншу кількість допоміжних операцій.
Для контрасту напишемо лінійний пошук індексу вручну, без firstIndex(of:), щоб побачити різницю в підході:
import Foundation
func linearSearch(_ array: [Int], target: Int) -> Int? {
for i in 0..<array.count {
if array[i] == target { return i }
}
return nil
}
Тепер думка, яку важливо зафіксувати словами: бінарний пошук виграє не тому, що «розумніший за if-else», а тому, що він використовує властивість даних — відсортованість.
7. Корисні нюанси
Бінарний пошук у реальному світі має багато варіантів: знайти перше входження, останнє, позицію вставки, працювати з дублікатами за контрактом тощо. Але ми свідомо не заглиблюємося: наша мета — впевнено писати базову версію і розуміти, чому вона коректна.
Якщо в масиві є дублікати, базовий бінарний пошук поверне яке-небудь із відповідних входжень. Це не помилка. Це означає лише те, що «індекс знайденого елемента» не зобов’язаний бути найлівішим або найправішим. Щоб гарантувати «перше» чи «останнє», алгоритм ускладнюється — і це окрема тема, якої сьогодні немає.
Ще один частий нюанс: бінарний пошук має використовувати те саме правило порівняння, що й сортування. Якщо ви відсортували за спаданням, а всередині пошуку використовуєте логіку «менше — ідемо праворуч», ви отримаєте дивні результати. Тому, якщо вам потрібно зберігати дані у спадному порядку, або змінюйте логіку бінарного пошуку під цей порядок, або не ускладнюйте собі життя й зберігайте дані за зростанням.
8. Типові помилки в бінарному пошуку
Помилка №1: запуск бінарного пошуку на невідсортованому масиві.
Це найпідступніша помилка, тому що іноді вона «випадково працює» на тестових даних. Але бінарний пошук спирається на порядок як на фундамент: якщо фундамент кривий, будинок може стояти… поки не подме вітер. Завжди сортуйте дані заздалегідь або зберігайте масив уже відсортованим.
Помилка №2: права межа right = array.count, а не array.count - 1.
array.count — це «розмір», але не індекс. Останній індекс — count - 1. Якщо переплутати, то рано чи пізно mid потрапить на count, і доступ array[mid] завершиться помилкою виконання через вихід за межі.
Помилка №3: оновлення меж без «переступання» через mid (left = mid замість left = mid + 1).
Так зʼявляється вічний цикл: mid перестає змінюватися, а умова left <= right лишається істинною. Алгоритм починає думати нескінченно — майже як людина перед вибором: «піца чи суші?». Тільки людина хоча б іноді таки обирає.
Помилка №4: плутанина між індексом і значенням.
У бінарному пошуку ми порівнюємо array[mid] з target, але рухаємо left/right як індекси. Якщо почати порівнювати mid з target, ви будете шукати не елемент, а «індекс, рівний 42». І це, звісно, теж задача… але зазвичай не та.
Помилка №5: неправильна обробка порожнього масиву.
Якщо масив порожній, array.count - 1 дасть -1, і поведінка меж стає дивною. Тому перевірка guard !array.isEmpty else { return nil } — не бюрократія, а захист від граничного випадку, який у реальних даних трапляється частіше, ніж хотілося б.
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ