Поиск делением пополам (двоичный поиск)

Поиск – одна из наиболее часто встречающихся в программировании задач, кроме того она очень удобна, чтобы испытывать различные структуры данных.

Для определенности примем, что поиск будет осуществляться в массиве

Var a:array [0..n-1] of item

Обычно тип item описывает запись с некоторым полем выполняющим роль ключа. Задача заключается в том, что необходимо найти элемент ключ которого = заданному аргументу поиска Х, т. к. нас интересует сам процесс поиска, то для простоты будем считать, что тип item включает только ключ.

Известно, что поиск можно сделать более эффективным если данные будут упорядочены, т. е. они будут подчинятся условию

Для любого k: 1<=k<n

Основная идея выбратьслучайный некоторый эле-т и сравнить его с аргументом поиска Х – если он =Х то поиск заканчивается, если он <Х то заключаем, что эл-ты с индексами меньшими или = m можно исключить из дальнейшего поиска, если>х то исключаются эл-ты с индексами =>m.

L:=0; R:=N-1; found:=false; {L и Rотмечают левый и правый конец секции массива где можно обнаружить искомый эле-т}

While (l<=R) and (not found) do

Begin M:=(любое значение между L и R); If a[m]=x then found:=trye Else if a[m]<x then L:=m+1 Else R:=m-1; End;

Инвариант

(L<=R)&(для любого k: 0<=k<L:ak<x)&(для любого k: R<k<n:ak>x)

Выбор совершенно произволен в том смысле, что корректность не зависит от него, однако этот выбор влияет на эффективность. Самый оптимальный вариант – средний элемент, т. к. на каждом шаге исключается половина массива. В результате мак. число сравнений порядка log n. Приведенный алгоритм выигрывает по сравнению с линейным где ожидаемое число сравнений n/2.

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

Быстрый алгоритм построен на инварианте

(для любого K: 0<=k< α: ak<x)& (для любого K: r<=k<n: ak =>x)

Поиск продолжается пока обе секции не накроят массив целиком.

L:=0; R:=N;

While L<R do Begin M:=(L+R) div 2 If a[m]<x then L:=m+1 Else R:=m; Условие окончания L=>R

Сортировка

Под сортировкой обычно понимают процесс перестановки объектов данного множества в определенном порядке. Метод сортировки называется устойчивым, если относительный порядок эл-тов с одинаковыми ключами не меняются при перестановке. Устойчивость сортировки желательна когда элементы отсортированы по каким-либо вторичным ключам, т. е. по свойствам не отраженным первичным ключом.

Сортировка массивов.

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

Меры эффективности алгоритмов. 1) Число необходимых сравнений ключей. 2) Пересылки эл-тов Эти числа определяются некоторыми числами от числа N. Хороший алгоритм требует порядка n log n числа сравнений.

Не нашли, что искали? Воспользуйтесь поиском: