Лекции по информатике (984119), страница 12
Текст из файла (страница 12)
Уроки деревьев поиска наводят на мысль, что прямые методы поиска могут быть чудовищно неэффективными. Для рассмотрения алгоритмов поиска предположим, что множество данных, в котором выполняется поиск, фиксировано, резидентно и допускает прямой доступ к каждому элементу: ъаг а: аггау[О..Х вЂ” 1] оГ1геш; где Нет, как всегда, комбинированная структура с ключевым полем 1:ед.
В результате поиска значения х в массиве а устанавливается индекс г, удовлстворяюгций условию а [1 ]. 1геу - х. Для простоты далее будем отождествлять клгоч и искомый элемент. 6.1.1 Линейный поиск Линейный поиск зак:почается в последовательном просмотре массива как списка с той же линейной сложностью: 0(Х). Просмотр выполняется в цикле, условие завершения которого таково: ° элемент найден: Ь: 10 < 1 < Ж) Й(а; = х); ° обход массива завершен, но искомый элемент не найден.
:-- О; 1 Выполнять поиск, пока индекс массива в пределах диапазона и пока искомое значение х не совпадет с очередным элементолл а[Ц 3 ъ.Ы1е (1 < Х) апс1 (аЯ <:> х) с1о —:- 1; 305 Стоимость выполнения такого цикла 4 у. е. за итерацию: 3 операции в предусловии и 1 операция в теле цикла. Ввиду возможности досрочного окончания цикла мы пе используем в этой программе цикл с параметром Гог.
Проанализируем условие продолжения цикла. Инвариант цикла,, т. е. условие, выполняющееся перед каждым увеличением индекса, г выглядит так: (О < г < Х) й~И; О < 7с < г: ав ф х) Вторая часть инварианта постулирует, что ранее, для всех к < г, совпадения также нс было.
Нарушая этот инвариант всеми способами по законам де Моргана и др., получаем условие прекращения цикла: ((г = Л')Ч (и; =:г)) ЫМК.: О < Й < ю': аь ф т) Это условие не только специфицирует результат поиска, .но и определяет именно первое вхождение искомого элемента с минимально возможным индексом, Поскольку элементы нумеруются нами с О, равенство г = 1У свидетельствует, что при обходе массива совпадения не было. Легко доказать и завершимость цикла: на каждом шаге значение г увеличивается на конечную величину 1., и, следовательно, за конечное число шагов достигнет предельного значения !У.
Ускорить поиск поможет барьерный элемент, который надо поместить в Х + 1-ый элемент массива, имеющий индекс Х: маг а: аггау ~О..Х) оГ 1пФеиег:, и из предусловия цикла будут удалены две из трех проверок: аЩ г-х; — О; жЫ1е а~11 <> х сто — 1; Постусловие никла также упростится.' 1а, = св) й(ЧЛ: О < А: < 1: аь ф т) Здесь мы, как и в случае со списком, перешли от цикла с параметром дискретным временем к циклу по сплошному участку массива. Издержки поиска с барьерным элементом это дополнительный элемент массива, инструкция присваивания для засылки барьерного элемента и несколько более сложная интерпретация кода. Осуществляя линейный поиск, мы предполагали равные шансы отыскания элемента на любом из У возможных мест.
Кроме того, очевидно, что этот метод поиска, единственно возможный для структур данных со строго последовательным доступом, .в частности, основанных на, поступательном или вращательном электромеханическом движении магнитного или оптического носителя. 6.1.2 Двоичный поиск Хорошо известно, что поиск данных в упорядоченном множестве с произвольным доступом к элементам более эффективен. В телефонных справочниках, словарях и энциклопедиях данные лексикографически упорядочены, Этот порядок, в свою очередь, базируется на алфавитноъс порядке букв' и дает простой и быстрый метод поиска, известный как метод половинного деления или просто, клишированный с английского, двоичный [бинарный) поиск.
Последнее название та,кже неудачно, как и двоичное [бин«чрное) дерево. Мы помним, что быстрый поиск данных в дереве был предопределен упорядоченной структурой дерева и су(цественныьс сокращением перебора, элементов. При каждом сравнении отб1засыв«злись половина из еще не1)ассмотренных элементов. В упо1эядо сс'нньсх множествах прямого доступа мы можем добиться такой же эффективности. Рассмотрим массив а, на, котором введено следующее отнопгенис порядка И:1</с<Я:аъ с <аь Для того, чтобы отбросить при поиске половину элементов, и продолжить поиск половинным делением, надо выяснить, в какой половине находится искомый элемент.
В силу данного отношения порядка, если выбрать некоторое промежутпочное значение индекса т, то отыскиваемый элемент х либо равен а, либо больше его, либо меньше. В первом случае поиск успешно заканчивается, во втором все элементы с индексами г < т можно исключить из дальнейшего поиска, и 1. его тем же методом для оставшихся элементов с индексами в диапазоне от т + 1 до Х. Именно в этом диапазоне обязан быть искомый элемент, если он вообще есть. В поссседнеъл с сучае., когда промежуточный элемент а меньше искомого, отбрасывается другая половина рассматриваемого множества. Приведем программу поиска методом половишсого деления. айаг Ь, К: шСеиег; ! Границы отрезка мосина а, в котором можегп находиться элемент х и долэюен Осу(де(тВАя7пься поиск з( 1оппдл Воо1еап; Ьеи1п Ь: 0; К:-- Х вЂ” 1; 1оппс! ь- Са1ве; ъъ(1п1е [ 1 < К) апс1 поС 1оппс1 с!о Ьеи1п ш: !' любое промежуточное значение между Ь и Л (; 1С а[ш~ -:- х СЬеп 1опп(1: -- Сгпе е1ве 1С' а[си~ < х СЬеп 1:--ш —,1 е1ве К,: — ш — 1 епс1:, епс1; Инвариант цикла, т.
е. условие, выполняющееся перед каждым (пагоъп [Ь < Л) А!И: 0 < lс < Ь: аъ < х) 1[И: Л < й < Х: аи > х) Постусловие цикла [при поиске отброшены отрезки, заведомо не содержащие искомого элемента): ("оипй Ъ' И1 > Л) 1[И: О < Ь- < Л: ар,.
< х) 1([И: Л < й < Ж; аи > х)) ~ «Благодарим алфавит за любезно предоставленные им упорядоченные буквыь — иии. 1ГЬ. гп 307 откуда следует, что элемент найден или его нет в просматриваемой последовательности: (а = х) сг ('сггс: О < л: < Х; ас ф х) Значение т в дипазонс 1... Ж вЂ” 2 может быть любым.
Но, вспоминая сбалансированные деревья, потребуем середины, чтобы при всяком сравнении отбрасывать половину бесперспективных элементов. При выборе среднего значения т максимальное число сратгнений равно [1од2 У) Р 1. То есть, поиск в упорядочс'пном множестве с прямым доступом к элементам также эффективен, как и в дереве поиска, и намного быстрее линейного поиска с числом сРавнений Хгг2. Однако вставка и Удаление элемента в УпоРЯдоченнУю таблицУ дороже,чем в дереве поиска. Эффективность поиска можно несколько повысить, отложив условный оператор проверки на равенство, вероятность успеха которого равна 1ггХ! Кроме того, упростим условие окончания цикла.
Оказывается, наивное желание закончить поиск при совттадении а,„с х /'онпз = 1гие в заголовке цикла избыточно и пересекается с условием сходимости границ поиска Ь и Л. Минимизированный инвариант цикла (И: О < к < Б: ас < х) ьт(И: Л < гс < Х: аь > х) видоизменяет критерий поиска до тех пор, пока интервал [Б, Л) не пуст. Поскольку поиск длится не более 1ои г'ст шагов, упрощенное предусловие экономит 2 1о~. ггт операций: отрицания г'оиггс1 и кон ыонкции его результата с отношением Б < Л.
(Другой стюсоб несколько ускорить тюиск вместо установки флага завершения цикла тоипд окончить итерации установкой некорректных границ 1. и К очередного интервала поиска. В результате такого тркгка предусловие цикла. также упроптсгсгтся.) 1.:-- О; К: — Х; 1' Барьерный индекс > максимального Х вЂ” 1. Если Л в результате ггоиска осгпамегпся равным тг, то поиск неудачен 3 тлгЫ1е 1.
< Й, с1о Ьеи1п тп: (1. ч К) с11ь 2; 11 а[тп) < х СЬеп 1.:=ш1 1 е1ве К; — ш епс1; Неслтотря на сокращение проверок, сложность этого тюиска все равно логарифмическая. Другой особенностьто этого тюиска является позднее обнаружение совпадения серединных элементов искомых отрезков ввиду стгсутствия их проверки на равенство. Докажем завершимость цикла с модифицированным предусловием. Отрицая предусловие Б < Л, получим условие окончания Б > Л.
Оно обязательно выполнится, если разность Л вЂ” 1 на каждом шаге поиска, убывает. Действительно, сначала Б < Л. Затем при выборе среднеарифметического т это соотношение сохраняется: на каждом шаге поиска либо Б увеличивается до т + 1, либо Л уменыпается до т и вссггда Ь < тп, < Л. Нри Б = Л повторение цикла заканчивается, Но для завершения поиска необходимо проделать еще несколысо операций. Во-первых, если Л = гсг, то поиск неудачен, ведь последнее неуспешное сравнение касается интервала [Л, Л), внутри которого всгсгбгще нет никаких элелтсгнтов! Н других же случаях, когда правая граница интервала поиска смещалась влево, следует предусмотреть се проверку на, равенство ал = х.
Эти издержки, конечно же невелики и, как и в случае вставки в дерево поиска, окупаются отысканием элемента с наименьшим среди равнозначных значений индексом: предыдущая версия программы поиска делением пополам вынесенной в начало цикла проверкой жадно хватала первый попавшийся элемент со значением х! 6.1.3 Поиск в таблице Отличие поиска в таблице от поиска в массиве закл1очается в том, что в таблицах ключ обычно является составным и имеет регулярную структуру, т. е, сам является массивом, чаще всего словом или строкой. Удобно ощэеделить строковый тип в Паскале так: Суре эСг1пи — аггау ~О..М вЂ” 11 оС' сЬаг: 1Ъгда основополагакпцее отношение лексикографического порядка на множестве строк за,дается следующим образом 1х — у) е (Чу: О < 1 < ЛХ; х, — у,) (х -с у) <=> (Лг: О < г < Л1: ((Ч1: О < ) < 1: х = у )й(х -~ у )) Проверка совпадения строк осуществляется их политерпым сравнением до первого расхождения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
