Методы программирования. Громов Ю.Ю - 109 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

109
Алгоритм В. (Бинарный поиск).
Дана таблица записей R
1
, R
2
, …, R
N
,
ключи которых расположены в
порядке возрастания: K
1
< K
2
< … < K
N
. Алгоритм используется для по-
иска в этой таблице заданного аргумента K.
B1. [Инициализация.] Установить l ← 1, и ← N.
B2. [Получение середины.] (На этом шаге известно, что если K
имеется в таблице, то справедливо условие K
l
≤ K ≤ K
и
.) Если u < l, алго-
ритм завершается неудачно; в противном случае необходимо присвоить
i ← (l+u)/2, чтобы i соответствовало примерно середине рассматривае-
мой части таблицы.
B3. [Сравнение.] Если K < K
i
, то перейти к шагу В4; если K > K
i
, то
перейти к шагуВ5; если K = K
i
, то алгоритм завершается успешно.
B4. [Изменение и.] Присвоить и ← i – 1 и вернуться к шагу В2.
B5. [Изменение l.] Присвоить l ← i + 1 и вернуться к шагу В2. ■
В таблицах 5 и 6 показаны два случая проведения бинарного поиска.
В первом случае осуществляется поиск числа 653, имеющегося в списке,
а во втором – числа 400, которое в списке отсутствует. Скобки показы-
вают положение указателей l и и, а подчёркнутое число – значение K
i
.
В обоих случаях поиск завершается после выполнения четырёх срав-
нений.
Таблица 5
[61
87 154
170
275
426
503
509
512
612
653
677
703
765
897
908]
61 87 154
170
275
426
503
509
[512
612
653
677
703
765
897
908]
61 87 154
170
275
426
503
509
[512
612
653]
677
703
765
897
908
61 87 154
170
275
426
503
509
512
612
[653]
677
703
765
897
908
Таблица 6
[61
87 154
170
275
426
503
509
512
612
653
677
703
765
897
908]
[61
87 154
170
275
426
503]
509
512
612
653
677
703
765
897
908
61 87 154
170
[275
426
503]
509
512
612
653
677
703
765
897
908
61 87 154
170
[
275
]
426
503
509
512
612
653
677
703
765
897
908
61 87 154
170
275]
[426
503
509
512
612
653
677
703
765
897
908
Для лучшего понимания работы алгоритма В представим описанную
процедуру поиска в виде бинарного дерева принятия решений, изобра-
жённого на рис. 38 для N = 16.

Страницы