Информатика / Алгоритмы и анализ данных

Двоичный поиск: максимальное число сравнений ключа

Двоичный поиск в отсортированном массиве отбрасывает половину диапазона после каждого трехстороннего сравнения. В худшем случае для n≥1 требуется не более ⌊log₂ n⌋+1 итераций.

Опубликовано: 15 октября 2026 г.Обновлено: 15 октября 2026 г.

Формула

C_{\max}(n)=\lfloor\log_2 n\rfloor+1,\quad n\ge1

Схема Сокращение диапазона в худшем случае

Для n=8 возможны размеры диапазона 8, 4, 2, 1. Четыре сравнения ключа с серединой; проверки условия цикла сюда не входят.

Обозначения

$n$: число элементов отсортированного массива, шт.
$Cₘₐₓ$: максимальное число итераций, сравнения с серединой

Условия применения

Массив должен быть отсортирован по тому же правилу, что и ключ поиска. На каждой итерации выбирается середина текущего диапазона, а сравнение имеет три исхода. Формула считает итерации, а не количество машинных операторов внутри реализации.

Ограничения

Для n=0 поиск завершается отдельной проверкой. Невыравненные стоимости доступа к памяти и дубликаты могут изменить практическое время. Последовательный поиск иногда быстрее на очень маленьких массивах из-за накладных расходов.

Подробное объяснение

Двоичный поиск поддерживает диапазон кандидатов [L,R]. Сравнение ключа с серединой дает один из трех результатов: равенство завершает поиск, меньше оставляет левую половину, больше — правую. После каждого сравнения рабочий диапазон сокращается примерно вдвое.

В худшем случае число сравнений ключа с элементом середины равно Cmax(n)=floor(log2 n)+1 для n≥1. Это именно итерации цикла поиска; проверку условия продолжения и присваивания границ в число сравнений ключа не включают.

Для n=8 цикл имеет размеры 8,4,2,1 и выполняет четыре сравнения. Рекуррентная запись C(0)=0, C(n)=1+C(floor(n/2)) для n≥1 показывает ту же границу.

Сортировка является обязательным условием. При дубликатах обычная версия находит один экземпляр, а поиск первой позиции меняет правило движения границы, сохраняя логарифмический порядок.

Сравнения ключей считаются как трёхисходная операция: меньше, равно или больше. Конкретная программа может реализовать её двумя логическими проверками, поэтому число выполненных операторов и число итераций — разные показатели стоимости.

Как пользоваться формулой

Проверьте сортировку массива по тому же отношению порядка, которое будет применяться к искомому ключу.
Для n≥1 вычислите логарифм по основанию два, округлите вниз и прибавьте единицу для оценки худшего случая.
При ручном поиске задайте включённые границы L и R и выберите середину с округлением индекса вниз.
Сравните ключ с серединой: при равенстве завершите поиск, иначе исключите середину и неподходящую половину.
Продолжайте до нахождения ключа или пустого диапазона; считайте сравнения с элементом, а не проверки цикла.

Историческая справка

Двоичный поиск относится к ранним алгоритмам работы с упорядоченными списками и получил современное распространение вместе с индексами и электронными таблицами. Его идея проста: сравнить с серединой и исключить половину кандидатов. В анализе алгоритмов она стала классическим примером логарифмической сложности, а оценка числа шагов выводится из последовательного деления диапазона на два. Исторические источники часто обсуждают варианты реализации отдельно от математической оценки; поэтому формула относится к модели сравнений, а не к конкретному языку программирования. Современные библиотеки добавляют поиск границ и работу с дубликатами, сохраняя тот же принцип уменьшения диапазона.

Историческая линия формулы

У двоичного поиска нет надежно установленного единственного автора в современной форме; это алгоритмическая идея, развивавшаяся в задачах поиска по упорядоченным данным. Формула сложности является результатом анализа деления диапазона пополам.

Пример

Для n=8 диапазон последовательно имеет размеры 8,4,2,1. На каждом размере выполняется одно сравнение ключа с элементом середины, поэтому C=4. Проверка по формуле: floor(log2 8)+1=3+1=4. Для n=1 получаем C=1. Проверку условия цикла и обновление индексов не считаем сравнениями с ключом. Для n=10 размеры могут быть 10,5,2,1, поэтому также требуется не более четырех сравнений: floor(log2 10)+1=4. Если ключ найден раньше, фактическое число сравнений меньше худшего случая, но граница сохраняется для любой позиции и неудачного поиска.

Частая ошибка

Нельзя применять формулу к неотсортированному массиву. Не путайте число итераций с числом операторов сравнения в исходном коде. Для n=0 нужен отдельный случай. Округление логарифма вверх без проверки соглашения о подсчете может дать другой вид границы. При поиске первой копии дубликата проверяйте измененные границы.

Практика

Задачи с решением

Восемь элементов

Условие. Сколько итераций в худшем случае нужно для n=8?

Решение. floor(log2 8)+1=3+1=4.

Ответ. 4

Один элемент

Условие. Сколько итераций для n=1?

Решение. floor(log2 1)+1=0+1=1.

Ответ. 1

Дополнительные источники

https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15122-s14/www/06-binsearch.pdf
https://www.cs.cmu.edu/~rdriley/121/notes/sorting/

Связанные формулы

Информатика

Индекс Жаккара: сходство через пересечение множеств

$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$

Индекс Жаккара показывает долю общих элементов в объединении двух множеств. Он принимает значения от 0 до 1: ноль означает отсутствие пересечения, а единица — совпадение множеств.

Информатика

Расстояние Левенштейна: вставки, удаления и замены

$D(i,j)=\min\{D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+[a_i\ne b_j]\}$

Расстояние Левенштейна — минимальное число вставок, удалений и замен стоимостью 1, превращающих одну строку в другую. Перестановка соседних символов отдельной операцией не считается.

Информатика

Неравенство Крафта: длины двоичных префиксных кодов

$\sum_{i=1}^{m}2^{-l_i}\le 1$

Неравенство Крафта проверяет, могут ли заданные длины двоичных слов образовать префиксный код: сумма 2 в степени минус длина не должна превышать единицу.