1. Зачем нужен бинарный поиск
Когда вы только начали программировать, поиск обычно выглядит так: «пройдёмся по массиву и сравним каждый элемент». И это абсолютно нормально — так делают все, включая взрослых дядь и тёть, если массив маленький. Но у этого подхода есть неприятный секрет: чем больше данных, тем больше времени вы тратите на «просто посмотреть». Бинарный поиск — это способ искать в отсортированном массиве, каждый раз выбрасывая половину вариантов.
Представьте, что вы ищете книгу в библиотеке. Можно идти по полкам слева направо, проверяя каждую (линейный поиск). А можно пользоваться тем, что книги отсортированы: посмотрели на середину, поняли «моя книга дальше», отрезали половину библиотеки, повторили. Бинарный поиск — это как раз «библиотекарь внутри вас», только без осуждающего взгляда за шум.
Сравним ощущения в виде маленькой таблицы:
| Подход | Требование к данным | Сколько сравнений (примерно) | Сложность |
|---|---|---|---|
| Линейный поиск | ничего | до n | |
| Бинарный поиск | массив отсортирован | до log2(n) | |
Идея O(log n) здесь простая: диапазон поиска каждый шаг уменьшается примерно в 2 раза. Было 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] завершится runtime-ошибкой выхода за границы.
Ошибка №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 } — не бюрократия, а защита от граничного случая, который в реальных данных встречается чаще, чем хочется.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ