AOP_Tom3 (1021738), страница 114
Текст из файла (страница 114)
Алгоритм В [Бинпрнапз поиск (В1пагу аеагсИ)). Дана таблица записей Я, Лз... 11ч, ключи которых расположены в порядке возрастания: Ка < Кз « .. - Кн, алгоритм используется для поиска в таблице заданного аргумента К. В1. [Инициализация.] Установить 1 ч — 1, и ч — 1У. В2. [Получение срединьь) [На этом шаге мы знаем, что если К имеется в таблице, то справедливо условие К~ < К < Ка. Более точное описание ситуации можно найти в приведенном ниже упр. 1.) Если и < 1, алгоритм завершается неудачно; в противном случае следует установить 1 е- [[1+ и)/2[, .чтобы 1 соответствовало примерно средине рассматриваемой части таблицы. В3. [Сравнение.) Если К ( К„перейти к шагу В4; если К > Ка, перейти к шагу В5; если К = К,, алгоритм успешно завершается.
В4. [Изменение и.) Установить и <- 1 — 1 и перейтн к шагу В2. В5. [Изменение Ц Установить 1+- 1+ 1 и перейти к шагу В2. 1 На рис. 3 приведена блок-схема алгоритма, а на рис. 4 показаны два случая проведения бинарного поиска: в первом разыскивается число 653, имеющееся в таблице, а во втором — число 400, отсутствующее в таблице.
Скобки показывают положеаие указателей 1 и и, а подчеркнутое число — — К;. В обоих случаях поиск завершается после выполнения четырех сравнений. а) Поиск 653: [061 087 154 170 275 426 503 509 512 612 653 677 703 765 897 908] 061 087 154 170 275 426 503 509[512 612 653 677 703 765 Я97 908) 061 087 154 170 275 426 503 509[512 612 653] 677 703 765 897 908 061 087 154 170 275 426 503 509 512 612[б53] 677 703 765 897 908 Ь) Поиск 400: 677 703 765 897 908] 677 703 765 897 908 677 703 765 897 908 677 703 765 897 908 677 703 765 Я97 908 (061 087 154 !70 275 426 503 509 512 612 653 [061 087 154 170 275 426 503] 509 512 612 653 061 087 154 !70[275 426 503] 509 512 612 653 061 087 154 170[275) 426 503 509 512 612 653 061 087 154 170 275)[426 503 509 512 612 653 Рис.
4. Примеры бинарного поиска. Программа В [Бинпрны!! поиск). Как и в программах из раздела 6.1. полагаем, что К; представляет собой полное слово, находягцееся по адресу ИВУ+1. В приведенном коде гН: — 1, г12 ив з и, г13 з— з 1. в~и и+- А". Переход к шагу В2. Переход, если К = К,. Вб. Изменение!.
1+-1+ 1. В2. Попечение с е ины. гА < — 1+ и. гА +- [гА/2]. (Изменяется также гХ ) Переход, если и < !. 1 < — ш!Оре!п!. ЕЕ11. Еи Переход. если К > К, В4. Изменение и. и < — ю — 1. Переход к шагу В2 9 Эта процедура не вполне удачно реализуется на компьютере М1Х в связи с небогатой арифметикой индексных регистров. Время работы составляет [18С вЂ” 105+12) и, где С = С1+ С2 -- количество произведенных сравнений [количество выполнений шага ВЗ) н 5 = 1 при успешном [или О при неуда пюм) исходе поиска. Обратите внимание, что операция в строке 08 — БНВ [еЬ!В г!КЬ! Ьшзгу 1 — — побитовый сдвиг вправо на единицу) -" допустима лишь в бннарньгх версиях И1Х; в общем случае ее следует изменить на МОЕ =1//2+1=, что приведет к увелнчени!о времени работы программы до [26С вЂ” 185+ 20)и.
Представление в ниде дерева. Для лучшего понимания работы алгоритма В представим описанную процедуру в виде бинарного дерева принятия решения, как показано на рис. 5, при К = 16. 01 БТАВТ 08 03 04 БН 05 Об 2Н 07 08 09 10 11 18 13 ЗН 1~ 15 1б 17 ЕИТ1 1 ЕИТ2 И 1МР 2Г 1Е БОССЕББ ЕИТ1 1,3 ЕИТА 0,1 1ИСА 0,2 БВВ 1 БТА ТЕМР СИР1 ТЕИР 30 ГА1ЬОВЕ ЬОЗ ТЕМР ЕОА К СИРА КЕУ,З ЛОЕ ЕВ ВИТ2 -1,3 ЛИР 2В 1 1 1 С1 С1 — 5 С 41 — 5 С+1 — 5 С+1 — 5 С+1 — 5 С+1 — 5 С+1 — 5 С С С С С2 С2 Рис. 5. Дерево сравнений, соответствующее бинарному поиску.для Х = 1б. При Х = 16 сначала согласно алгоритму сравниваются К и Кв, 'на рисунке зто показано корневым узлом ®. Затем, если К < Кю алгоритм переходит в левое поддерево и сравниваются К с К4, точно твк же при К > Кв будет выполняться работа с правым поддеревом.
Неудачный поиск приведет в один из внешних "квадратных" узлов, пронумерованных от [о) ло Е, например узел (б1 будет достигнут нами только при Кв с К < Кт. Бинарное дерево, соответствующее бинарному поиску по Л' записям, может быть построено следующим образом: если Х = О, дерево представляет собой просто один узел (Я. В противном случае корневой узел— (.Ч/2) При атом левое поддерево представляет собой бинарное дерево с (Л/21 — 1 узлами, а правое — с (Л/21 узлами (все числа в узлах увеличены на (Х/21). Точно так в виде бинарного дерева с Х узлами, в котором все узлы пронумерованы от 1 до Ж, может быть представлен любой алгоритм поиска в упорядоченной таблице длиной Л' (если только алгоритм не выполняет излишние сравнения). Верно и обратное — любое бинарное дерево соответствует некоторому методу поиска и упорядоченной таблице; достаточно просто пометить узлы ~Е (, ) И (2.) И ИН ® Е (1) в симметричном порядке слева направо.
Если аргумент поиска алгоритма В равен К1о, алгоритм выполняет сравнения К > Кв, К < Кип К = К1о. На рис. 5 зто соответствует пути от корня дерева к вершине (ю). Точно так поведение алгоритма В при поиске других ключей соответствует некоторому пути из корня дерева. Метод построения бинарных деревьев, соответствующих алгоритму В, позволяет легко доказать с помощью индукции по Ж следуюшую теорему. Теорема В. Для 2" ' < Л' < 2" успешный поиск по алгоритму В требует (ппп 1, шах к) сравнений; неудачный поиск прн 2" ' < Х < 2" — 1 требует й — 1 либо и сравнений. 1 Дальнейший анализ бинарного поиска. (Читателям, для которых математика не представляет интереса, рекомендуем пропустить материал до формулы (4).) Представление в виде дерева показывает нам также простой путь вычисления среднего числа сравнений.
Пусть См — среднее число сравнений при успешном поиске; предположим также, что все Ж ключей равновероятны в качестве аргумента поиска. Среднее число сравнений при неудачном поиске — С'; все Ю + 1 интервалов внутри и вне граничных значений также равновероятны. Тогда по определению длин внутреннего и внешнего путей длина внутреннего пути дерева См — 1+ Х длина внешнего пути дерева %+1 Из 2.3.4.5 — (3) видно, что длина внешнего пути всегда на 2й' больше длины внутрен- него пути.
Отсюда следует несколько неожиданное соотношение между См и С~.. (2) р + ц((18ж) + 2) — 20з')+'. (3) (См. 5.3.1-(34).) Из формул (2) и (3) мы можем вычислить точные средние значения количества сравнений, полагая, что все аргументы поиска равновероятны. К=1 См = 1 С' =1 10 11 12 13 2з 3 3 — ' Зз зв зв 3Ы зи й й зз зв 14 15 16 з в в Зв 4 4з 1в ы 2 3 4 5 6 11 1з 2 21 22 1з 2 2з 2в 2в з 7 8 9 23 25 21 3 Зз Зв з зв В общем случае при й = (18 1з') мы имеем следующее: Са = /с+1 — (2"+' — й — 2)~У = 18У вЂ” 1+в+ (1с+2)/У, С~~~ = )в + 2 — 2~в'~/(У+ 1) = 1$Р + 1) + в (4) где 0 < в, в' < 0.0861 (см.
5.3.1-(35)) . Итак, алгоритм В никогда не делает более ()8 )т') + 1 сравнений; среднее количество сравнений при успешном поиске составляет около 18Х вЂ” 1. Никакой друтой Эта формула, выведенная Т. Н. Хиббардом (Т. 51. Н1Ьоагй) [.7АСМ 9 (1962), 16 — 17), справедлива для всех методов, соответствующих бинарным деревьям; другими словами, она справедлива для всех методов, не использующих излишних сравнений.
Дисперсия среднего числа сравнений при успешном поиске также может быть выражена через дисперсию среднего числа сравнений при неудачном поиске (см. упр. 25). На основании приведенных выше формул мы можем сказать, что "наилучший" путь поиска методом сравнения тот, дерево которого имеет минимальную длину внешнего пухи среди всех бинарных деревьев с 1з внутренними узлами. К счастью, можно доказать, что в етом смысле алгоритм В оптимален для любого Т (как помните, в упр.
5.3.1-20 было доказано, что бинарное дерево имеет минимальную длину пути тогда и только тогда, когда все внешние узлы расположены не более чем на двух соседних уровнях). Отсюда следует, что длина внешнего пути дерева, соответствующего алгоритму В, равна метод поиска, основанный на сравнении ключей, не может превзойти этот результат. Среднее время работы программы В составляет приблизительно (18 18 Х вЂ” 16) и лля успешного поиска, (1818% + 12)и для неудачного поиска (5) (в предположении равновероятиых исходов поиска).
Важное изменение. Вместо трех указателей (1, 1 и и) в процессе поиска можно использовать только два: текущее положение 1 и величину его изменения б. После каждого сравнения, не давшего равенства, мы можем установиты < — 1х б и б < — б/2 (приблизительно). Это вполне возможный путь, хотя и требующий исключительного ваимаиия к мельчайшим деталям, как в приведенном ниже алгоритме. Более простые подходы будут неработоспособны. Алгоритм 11 (Одноробнмй бинарный поиск (Вгя/опи Ипату зеогсЬ)).
Дана таблица записей Вы Вю..., Вн, ключи которых расположены в порядке возрастания: К, < Кз < . с Кл. Алгоритм обеспечивает поиск заданного аргумента К. В случае четного Х алгоритм будет обращаться к Фиктивному ключу Ке, значение которого должно быть равно — оо (или любому значению, меиыпему К).
Алгоритм работает в предположении, что Х > 1. Ш. (Инициализация,] Установить 1 < — 1)У~2~1, пз < — (Х/2) . Ю2. (Сравнение.) Если К с К„перейти к шагу 1'3; если К > Кн перейти к шагу 1:4; если К = Кн алгоритм успешно завершен. 113. (Уменьшиты.] (Мы определили интервал продолжения поиска, содержащий нз или ьп — 1 записей; 1 указывает на первый элемент справа от интервала.) При т = 0 алгоритм завершается неудачно.
В противном случае следует сначала установиты ~ — 1 — (гп/2), а затем — т < — (т/2) и перейти к шагу С2. 114. (Увеличение Ц (Мы определили интервал продолжения поиска, содержащий гп или т — 1 записей; 1 указывает иа первый элемент слева от интервала.) При т = 0 алгоритм завершается неудачно. В противном случае следует сначала установить 1 < — 1+ (гп/21, а затем — т < — (т/2) и перейти к шагу (12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
