Сублинейное время

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

Пожалуй, самым известным примером такого рода является алгоритм бинарно- го поиска. Имеется отсортированный массив A из n чисел; требуется определить, принадлежит ли массиву заданное число p. Конечно, задачу можно решить чтени- ем всего массива, но нам хотелось бы действовать намного более эффективно — проверять отдельные элементы, используя факт сортировки массива.

Алгоритм проверяет средний элемент A и получает его значение (допустим, q), после чего q сравнивается с p. Если q = p, поиск завершается. Если q > p, то значение p может находиться только в нижней половине A; с этого момента верхняя половина A игнорируется, а процедура поиска рекурсивно применяется к нижней половине. Если же q < p, то применяются аналогичные рассуждения, а поиск рекурсивно продолжается в верхней половине A.

Суть в том, что на каждом шаге существует некая область A, в которой может находиться p; при каждой проверке размер этой области уменьшается вдвое. Каким же будет размер «активной» области A после k проверок? Начальный размер равен n, поэтому после k проверок он будет равен максимум .

Учитывая это обстоятельство, сколько шагов понадобится для сокращения активной области до постоянного размера? Значение k должно быть достаточно большим, чтобы  , а для этого мы можем выбрать k = log2n. Таким образом, при k = log2 n размер активной области сокращается до константы; в этой

точке рекурсия прекращается, и поиск в оставшейся части массива может быть

проведен за постоянное время.