Номер §4 ПМ 6

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

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

Итак, даже в длинной упорядоченной последовательности поиск методом половинного деления остаётся сравнительно быстрым.