Идея деления пополам
Алгоритм сравнивает искомое значение со средним элементом отсортированного массива. Если оно меньше, поиск продолжается в левой половине, если больше – в правой. Так область поиска сокращается вдвое на каждом шаге.
Количество шагов равно количеству раз, которое n можно разделить на два до единицы. Это и есть логарифм по основанию 2: например, log₂ 1024 = 10, потому что 2¹⁰ = 1024.
Целое число сравнений и худший случай
Логарифм может быть дробным, а число сравнений – только целое. Для n = 1 000 000 получаем log₂ n ≈ 19,93. Берём целую часть 19 и прибавляем единицу за последнюю проверку: в худшем случае 20 сравнений.
Граничный случай показывает разницу: при n = 1023 хватит 10 сравнений, а при n = 1024 уже 11, хотя логарифм у второго значения ровно 10. Поэтому правило «целая часть плюс один» точнее, чем простое округление.
Сравнение с линейным поиском
Линейный поиск в среднем просматривает половину массива, а в худшем случае – весь массив. Для миллиона элементов это 500 000 сравнений в среднем против двадцати у бинарного поиска, и разрыв растёт вместе с размером данных.
Рост даже очень больших массивов практически не увеличивает число шагов: для миллиарда элементов нужно всего 30 сравнений, поскольку log₂ 10⁹ ≈ 29,9. Этим объясняется популярность индексов и отсортированных таблиц.
Условия применимости
Бинарный поиск требует, чтобы данные были отсортированы и доступны по индексу за постоянное время. В связном списке он теряет преимущество, так как перейти к середине можно только последовательным обходом.
Если данные часто меняются, придётся поддерживать порядок элементов, что может стоить дороже поиска. В таких случаях рассматривают сбалансированные деревья или хеш-таблицы, но их выбор зависит от задачи.
Типичные ошибки
Часто округляют логарифм вверх без добавления единицы или вниз без неё и получают число на один шаг меньше реального. Ещё одна ошибка – подставить основание 10 и получить число десятичных разрядов, а не число сравнений.
Другая ошибка – считать, что алгоритм всегда работает за максимальное число шагов. Это верхняя граница; удачное попадание в середину завершает поиск раньше, а среднее значение лишь немного меньше максимума.
Где применять оценку
Оценка полезна при выборе структуры данных, анализе сложности O(log n), проектировании индексов базы данных и подготовке к собеседованиям. Она позволяет быстро прикинуть число обращений при росте объёма данных.
Фактическая скорость зависит от процессора, кэша и стоимости сравнения. Для критичных к производительности систем результаты теоретической оценки подтверждайте измерениями на реальных данных.
Связь с двоичным деревом
Шаги бинарного поиска соответствуют уровням сбалансированного двоичного дерева. На глубине d помещается 2^d − 1 элементов суммарно, поэтому дерево глубиной 20 вмещает больше миллиона узлов, ровно 1 048 575.
Эта связь объясняет и обратную задачу: зная допустимое число сравнений k, вы получите максимальный размер массива 2^k − 1. Для десяти сравнений это 1023 элемента, для двадцати – 1 048 575.
Для наглядности возьмём массив из 100 элементов. Логарифм равен примерно 6,64, целая часть 6, значит худший случай составляет 7 сравнений. Прямой перебор в среднем потребовал бы около 50 просмотров, а в худшем случае – все 100.
Формула расчёта
шаги = ⌊log₂ n⌋ + 1; log₂ n = ln n ÷ ln 2
Проверенные примеры
Сколько сравнений потребуется бинарному поиску в массиве из 1 000 000 элементов?
log₂ 1 000 000 ≈ 19,93; целая часть 19, плюс единица – 20 сравнений в худшем случае.
Сколько сравнений нужно для 1024 элементов?
log₂ 1024 = 10; ⌊10⌋ + 1 = 11 сравнений в худшем случае.
Как пользоваться онлайн-калькулятором
- Введите число элементов массива, например 1000000.
- Оставьте основание логарифма равным 2.
- Нажмите «Вычислить» и получите значение log₂ n.
- Возьмите целую часть результата и прибавьте единицу – это худшее число сравнений.