8. Бинарный поиск и поиск по бинарному дереву

Поиск в массиве записей может быть выполнен значительно быстрее, если они предварительно отсортированы по возрастанию или убыванию ключей, которые используются для поиска. Пусть исходный массив записей a₁,a₂,…,a_n отсортирован таким образом, что значения ключей: f(a₁) < f(a₂) < … < f(a_n). Тогда бинарный поиск выполняется следующим образом: Пусть k – аргумент поиска, тогда:

1. На первом шаге вычисляется индекс среднего элемента р=n/2. Если значение p получается не целым, то оно может округляться в любую сторону (но всегда в одну).

2. Если k = f(a_p), то – конец алгоритма. Результатом будет индекс элемента p этого массива.

3. Если это условие не выполняется, то проверяется следующее условие: k < f(a_p). При его выполнении поиск должен быть продолжен в левой половине массива, т.е. среди элементов: a₁,a₂,…,a_p-1. В противном случае, т.е. при k > f(a_p), поиск должен быть продолжен в другой половине, т.е.: a_p+1,a_p+2,…,a_n.

В выбранной половине опять определяется средний элемент, и процедура повторяется до тех пор, пока не встретится запись с заданным ключом или пока не останется один не просмотренный элемент. Если этот элемент имеет ключ k, то процесс завершился успешно, если нет, то запись с заданным ключом отсутствует.

По сравнению с линейным поиском считается, что бинарный поиск становится более эффективным, когда n > 20.

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

Реализация:

1) Итерационный вариант: k – аргумент поиска

a[1..n] – массив ключей, в которых производится поиск

L, h – переменные, индексы верхней и нижней границы зоны поиска

BS = 0 – запись с заданным ключом отсутствует, в противном случае BS = i – индекс элемента

2) Рекурсивный вариант.

В рекурсивном варианте будем считать, что алгоритм бинарного поиска реализуется функцией BS (k, L, h), k – аргумент поиска, h, L – верхняя и нижняя границы поиска.

Поиск по бинарному дереву:

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

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

1. Первую запись входной последовательности сопоставляют с корнем дерева.

2. Для каждой следующей записи ключ сначала сравнивается с ключом корня. Если он меньше, чем ключ корня, то далее сравнивается с ключом левого потомка; если больше, то с ключом правого. Если потомок для сравнения отсутствует, то формируется новая вершина дерева, с которой сопоставляется очередная запись.

3. Шаг 2 повторяется до тех пор, пока не будет просмотрена вся входная последовательность записей.

Поиск записи с заданным ключом осуществляется в точности по рассматриваемой процедуре.

Сложность алгоритма поиска по дереву определяется высотой дерева и колеблется в пределах от O(Log2n) до O(n).