Стр. 25 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
23
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4.3.2. Бинарный поиск в статических таблицах
(метод деления отрезка пополам)
Пусть таблица хранится в памяти с произвольным методом доступа
(прямой
RAM
). Пусть имена в таблице имеют естественный порядок, то есть
1
+
<
i
i
x x
. Тогда интервал поиска можно сокращать вдвое после каждого
сравнения искомого z с некоторым
i
x
, если каждый раз выбирать
i
x
в середине
интервала поиска (или интервала неопределенности).
Алгоритм №4.
l =
1
// нижняя
h = n // верхняя
while l <= h
{
m = (l+h)/2 // медиана
╓
║ z = xm : < успех >;
║
case ─╢ z < xm : h = m –
1
;
║
║ z > xm : l = m +
1
;
╙
}
<неудача>
Очевидно, поскольку интервал сокращается в 2 раза, время решения равно
О(
2
log
n
).
Процесс решения задачи по алгоритму 4 можно представить в виде
бинарного дерева, вершины которого соответствуют операциям сравнения
z
c
x
i
. Если результатом сравнения является равенство, то поиск заканчивается в
этой вершине. Если
z
оказалось меньше, то переходим к левому сыну данной
вершины, если
z>x
i
, то к правому звену (сыну).
Пример
:
Составим дерево бинарного поиска из 10 элементов (ключей).
n
= 10.
