Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Бинарный поиск

Читайте также:
  1. XXXIX. ПОЛЕТЫ ПРИ ПОИСКЕ И СПАСАНИИ
  2. Абу Зарр, R, – в поисках истины
  3. Алгоритмы глобального поиска
  4. Анализ проблем утопических проектов и поиск путей их преодоления.
  5. Базы данных, информационно-поисковые системы
  6. Безработные по способам поиска работы
  7. Бессонные ночи в поисках знаний

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

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

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

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

Программная иллюстрация бинарного поиска в упорядоченном массиве приведена в следующем примере, где a - исходный массив, key - ключ, который ищется; функция возвращает индекс найденного элемента или EMPTY - если элемент отсутствует в массиве.

 

{===== Программный пример 2 =====}

Function BinSearch(a: SEQ; key: integer): integer;

Var b, e, i: integer;

begin

b:=1; e:=N; { начальные значения границ }

while b<=e do { цикл, пока интервал поиска не сузится до 0 }

begin i:=(b+e) div 2; {середина интервала }

if a[i]=key then

begin BinSearch:=i; Exit; {ключ найден - возврат индекса }

end else

if a[i]<key then b:=i+1 { поиск в правом подинтервале }

else e:=i-1; { поиск в левом подинтервале }

end; BinSearch:=EMPTY; { ключ не найден }

end;

Трассировка бинарного поиска ключа 275 в исходной последовательности:

75, 151, 203, 275, 318, 489, 524, 519, 647, 777 представлена в таблице 1.

 

Таблица 1

Итерация b e i K[i]
         

 

Алгоритм бинарного поиска можно представить и несколько иначе, используя рекурсивное описание. В этом случае граничные индексы интервала b и e являются параметрами алгоритма.

Рекурсивная процедура бинарного поиска представлена в программном примере 3.6. Для выполнения поиска необходимо при вызове процедуры задать значения ее формальных параметров b и е - 1 и N соответственно, где b, e - граничные индексы области поиска.

 

{===== Программный пример 2 =====}

Function BinSearch(a: SEQ; key, b, e: integer): integer;

Var i: integer;

begin

if b>e then BinSearch:=EMPTY { проверка ширины интервала }

else begin

i:=(b+e) div 2; { середина интервала }

if a[i]=key then BinSearch:=I {ключ найден, возврат индекса }

else if a[i]<key then { поиск в правом подинтервале }

BinSearch:=BinSearch(a,key,i+1,e)

else { поиск в левом подинтервале }

BinSearch:=BinSearch(a,key,b,i-1);

end; end;

 

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


Дата добавления: 2015-07-15; просмотров: 123 | Нарушение авторских прав


Читайте в этой же книге: Краткий курс лекций | Хранение информации | Классификация структур данных | Операции над структурами данных | Операции. Выражения | Лекция 3 Структура программы. | Безусловного перехода, | Лекция 11. Подпрограммы-функции. | Interface | Лекция 13. Ссылочный тип. |
<== предыдущая страница | следующая страница ==>
Лекция 14. Алгоритмы поиска и выборки.| Лекция 15. Сортировка

mybiblioteka.su - 2015-2024 год. (0.006 сек.)