Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
38.
Бинарный поиск
Наиболее эффективным методом поиска в упорядоченном файле, представленном в виде массива, является двоичный (бинарный) поиск. Алгоритм был предложен Дж. В. Мочли. Его идея заключается в следующем. Аргумент поиска сравнивается с ключом средней записи, если они равны, то поиск заканчивается удачно, в противном случае поиск продолжается либо в левой половине файла, либо в правой половине файла.
Каждое сравнение при двоичном поиске сокращает в два раза число записей, которые надо исследовать. Таким образом, максимальное число сравнений, которое необходимо сделать, равно [log2n] + 1. Среднее число сравнений при удачном поиске приближенно равно log2(n – 1).
Можно показать, что ни один алгоритм, основанный на сравнении ключей, не может иметь меньшую вычислительную сложность, чем алгоритм двоичного поиска. Максимальное число сравнений при удачном поиске не менее [log2n].
Основным недостатком двоичного поиска является то, что он применим лишь к данным, представленным в виде массива.
Приведем одну из наиболее популярных форм реализации метода бинарного поиска. В ней используются два указателя, l и u, которые указывают верхнюю и нижнюю границы поиска.
Алгоритм В (Бинарный поиск (Binary search)). Дана таблица записей r1r2r3…rn, ключи которых расположены в порядке возрастания: K1<K2<….<Kn. Алгоритм используется для поиска в массиве заданного аргумента К.
В1. [Инициализация.] Установить l:=1, u:=n.
В2. [Получение середины.] Если u < l, алгоритм завершается неудачно; в противном случае следует установить , чтобы i соответствовало примерно середине рассматриваемой части массива. u)/2(l:i
ВЗ. [Сравнение.] Если K<Ki, перейти к шагу В4; если К > Кi перейти к шагу В5; если К = Ki, алгоритм успешно завершается.
В4. [Изменение u.] Установить u:=i-1 и перейти к шагу В2.
В5. [Изменение l.] Установить l:=i+1 и перейти к шагу В2.
На рис. 1 приведена блок-схема алгоритма бинарного поиска.
Рис.1. Бинарный поиск
Представление в виде дерева. Для лучшего понимания работы алгоритма В представим описанную процедуру в виде бинарного дерева принятия решения, как показано на рис. 2, при n = 16.
При n=16 сначала согласно алгоритму сравниваются K и K8; на рисунке это показано корневым узлом 8 в кружочке. Затем, если K<K8, алгоритм переходит в левое поддерево и сравниваются K с K4; точно также при K>K8 будет выполняться работа с правым поддеревом. Неудачный поиск приведет в один из внешних «квадратных» узлов, пронумерованных от 0 до n , например, узел 6 будет достигнут только при K6<K<K7.
Рис.2. Дерево сравнений, соответствующее бинарному поиску для n=16.
Фибоначчиев поиск
Рассмотрим одну интересную модификацию двоичного поиска, предложенную Д.Е.Фергюсоном, – фибоначчиев поиск.
Последовательность чисел Фибоначчи определяется рекуррентным соотношением:
F0=0, F1=1, Fi=Fi-1+Fi-2 при i≥2.
В последовательности Фибоначчи
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
каждое число равно сумме двух предыдущих
Числа Фибоначчи позволяют разработать альтернативу бинарному поиску. Для некоторых компьютеров предлагаемый метод предпочтителен в связи с тем, что в нем используются только сложение и вычитание (без деления на 2).
Дерево Фибоначчи порядка k имеет Fk+1 -1 внутренних (на рис.3. – круглых) и Fk+1 внешних (на рис.3. квадратных) узлов. Строится оно следующим образом:
Если k=0 или k=1, дерево вырождается в 0 .
Если k≥2, корнем является Fk ; левое поддерево представляет собой дерево Фибоначчи порядка k-1; правое поддерево представляет собой дерево Фибоначчи порядка k-2 с числами, увеличенными на Fk.
Числа двух дочерних узлов каждого внутреннего узла отличаются от него на одну и ту же величину – число Фибоначчи (например, на рассматриваемом рисунке 5=8-F4 и 11=8+F4). Если разница на каком-либо уровне составляет Fj , то на следующем уровне она будет равна Fj-1 для левой ветви и Fj-2 – для правой. Так, например, 3=5-F3, а 10=11-F2.
Комбинируя эти наблюдения с механизмом распознавания внешних узлов, мы получим следующий алгоритм поиска.
Рис.3. Дерево Фибоначчи порядка 6
Алгоритм Фибоначчиева поиска:
Дан файл записей r1r2r3…rn , ключи которых расположены в порядке возрастания K1<K2<….<Kn. Алгоритм осуществляет поиск заданного аргумента K.
Предположим, что n+1 представляет собой число Фибоначчи Fk+1. В общем случае, когда n + 1 не равно какому-либо числу Фибоначчи, в качестве Fj надо рассмотреть ближайшее число Фибоначчи большее n + 1.
F1. (Инициализация) i:=Fk; p:=Fk-1 ; q:=Fk-2 .
F2. (Сравнение) Если K<Ki, перейти к шагу F3, если K>Ki , перейти к шагу F4; если K=Ki алгоритм успешно завершается.
F3. (Уменьшение i) Если q=0, алгоритм закончился неудачно. В противном случае следует установить i:=i-q; p:=p-q; q↔p (обмен значений p и q) ; затем перейти к шагу F2.
F4. (Увеличение i) Если p=1, алгоритм завершается неудачно. В противном случае следует сначала установить i:=i+q; p:=p-q; q:=q-p и перейти к шагу F2.