5.6. Логарифмический поиск

Логарифмический (бинарный или метод деления пополам) поиск данных применим к сортированному множеству элементов размещение которого выполнено на смежной памяти. Для большей эффективности поиска элементов надо, чтобы пути доступа к ним стали более короткими, чем просто последовательный перебор. Наиболее очевидный метод: начать поиск со среднего элемента, т.е. выполнить сравнение с элементом Результат сравнения позволит определить, в какой половине последовательности продолжить поиск, применяя к ней ту же процедуру, и т.д. Основная идея бинарного поиска довольно проста, однако «для многих хороших программистов не одна попытка написать правильную программу закончилась неудачей». Чтобы досконально разобраться в алгоритме, лучше всего представить данные виде двоичного дерева сравнений, которое отвечает бинарному поиску.

Двоичное дерево называется деревом сравнений если для любой его вершины (корня дерева или корня поддерева) выполняется условие:

Пусть на очередном шаге деления пополам оказалось, что необходимо выполнить поиск среди элементов . В качестве корня принимается элемент где наибольшее целое, меньшее или равное Левое поддерево располагается в векторе а правое поддерево — в векторе На рис. 5.6 показан пример двоичного дерева сравнении, ребра которого неявно выражаются рассмотренными выше отношениями между индексами элементов

Рис. 5.6. Пример дерева сравнений, отвечающего бинарному поиску среди сортированных элементе: 3,5,7,9,12,19,27,44

Поиск элемента z среди методом деления пополам представлен в алгоритме 5.8.

Алгоритм 5.8. Логарифмический поиск

(см. скан)

Средняя сложность бинарного поиска среди элементов сравнима с высотой двоичного дерева (рис 5.6). В худшем случае искомый элемент может оказаться либо на последнем уровне, либо вообще не будет найден. На каждом уровне необходимо выполнить определенное число сравнений. В п. 5.4 установлено, что уровней в дереве Значит, сложность поиска является логарифмической что оправдывает и название самого метода поиска.

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