Лекция
Привет, Вы узнаете о том , что такое поиск с барьером, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое поиск с барьером , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
поиск с барьером – это модификация алгоритма последовательного поиска, ускоряющая процесс путем определения граничного элемента.
Существует модификация алгоритма последовательного поиска, которая ускоряет поиск. Эта модификация является небольшим усовершенствованием рассмотренного алгоритма поиска.
Идея поиска с барьером состоит в том, чтобы не проверять каждый раз в цикле условие, связанное с границами множества. Это можно обеспечить, установив в данном множестве так называемый барьер. Под барьером понимается любой элемент, который удовлетворяет условию поиска. Тем самым будет ограничено изменение индекса.
Выход из цикла, в котором теперь остается только условие поиска, может произойти либо на найденном элементе, либо на барьере. Существует два способа установки барьера: дополнительным элементом или вместо крайнего элемента массива.
Алгоритм линейного поиска можно упростить, избавившись от проверки дополнительного условия, если быть уверенным, что в массиве обязательно присутствует элемент, совпадающий с образцом. Иногда истинность этого условия следует из знания того, как строился массив и образец поиска. Но можно добиться выполнения этого условия принудительно, соорудив в массиве "барьер", препятствующий выходу поиска за границы массива. С этой целью массив расширяется на один элемент и в качестве последнего элемента записывается "барьер" - образец поиска. В этом случае поиск всегда найдет образец. Если образца нет среди "родных" элементов массива, то он встретится в конце в виде "барьера".
Для упрощения больше подходит вторая версия алгоритма линейного поиска. Приведу реализацию этой схемы:
Заметьте, сам метод никаких барьеров не строит. Он лишь формулирует предусловие, требующее существование барьерного элемента в массиве. Ответственность за выполнение предусловия лежит на клиенте. Тот, кто вызывает метод, тот и должен заботиться о выполнении предусловия. Таковы принципы проектирования по контракту. Конечно, можно построить другую реализацию, где ответственность за построение барьера берет на себя сам метод.
Заметим, так же что поиск с барьером работает быстрее, но временная сложность алгоритма остается такой же O(n), где n – количество элементов множества. Гораздо больший интерес представляют методы, не только работающие быстро, но и реализующие алгоритмы с меньшей сложностью.
Исследование, описанное в статье про поиск с барьером, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое поиск с барьером и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Из статьи мы узнали кратко, но содержательно про поиск с барьером
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов