Алгоритмы поиска

Алгоритм линейного поиска заданного элемента на множестве, осуществляемый путем последовательного сравнения очередного рассматриваемого значения с искомым до тех пор, пока эти значения не совпадут. Метод бинарного (двоичного) поиска, его модификации.

Рубрика Программирование, компьютеры и кибернетика
Вид реферат
Язык русский
Дата добавления 19.06.2022
Размер файла 62,1 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

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

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

Идея этого метода заключается в следующем. Множество элементов просматривается последовательно в некотором порядке, гарантирующем, что будут просмотрены все элементы множества (например, слева направо). Если в ходе просмотра множества будет найден искомый элемент, просмотр прекращается с положительным результатом; если же будет просмотрено все множество, а элемент не будет найден, алгоритм должен выдать отрицательный результат.

Алгоритм последовательного поиска

Шаг 1. Полагаем, что значение переменной цикла i=0.

Шаг 2. Если значение элемента массива x[i] равно значению ключа key, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицу i=i+1.

Шаг 3. Если i<k, где k - число элементов массива x, то выполняется Шаг 2, в противном случае - работа алгоритма завершена и возвращается значение равное -1.

При наличии в массиве нескольких элементов со значением key данный алгоритм находит только первый из них (с наименьшим индексом).

int LinearSearch(int *x, int k, int key){

int i = 0;

for ( i = 0 ; i < k ; i++ )

if ( x[i] == key )

break;

return i < k ? i : -1;

}

Время выполнения данного алгоритма поиска для вещественных чисел , где n - количество элементов множества, а - точность. Поиск на дискретном множестве из n элементов осуществляется в худшем случае за n итераций, а в среднем этот алгоритм требует n/2 итераций цикла. Следовательно, временная сложность последовательного поиска пропорциональна O(n). Никаких ограничений на порядок элементов в массиве данный алгоритм не накладывает.

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

Достоинства последовательного поиска заключаются в том, что он прост в реализации, не требует сортировки значений множества, дополнительной памяти и дополнительного анализа функций. Следовательно, может работать в потоковом режиме при непосредственном получении данных из любого источника.

Существует модификация алгоритма последовательного поиска, которая ускоряет поиск. Эта модификация является небольшим усовершенствованием рассмотренного алгоритма поиска.

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

Выход из цикла, в котором теперь остается только условие поиска, может произойти либо на найденном элементе, либо на барьере. Существует два способа установки барьера: дополнительным элементом или вместо крайнего элемента массива.

//описание функции последовательного поиска с барьером

int LinearSearchWithBarrier(int *x, int k, int key){

x = (int *)realloc(x,(k+1)*sizeof(int));

x[k] = key;

int i = 0;

while ( x[i] != key )

i++;

return i < k ? i : -1;

}

Заметим, что поиск с барьером работает быстрее, но временная сложность алгоритма остается такой же O(n), где n - количество элементов множества. Гораздо больший интерес представляют методы, не только работающие быстро, но и реализующие алгоритмы с меньшей сложностью.

Бинарный (двоичный) поиск

Бинарный (двоичный, дихотомический) поиск - это поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Поиск заканчивается при совпадении искомого элемента с элементом, который является границей между частями множества или при отсутствии искомого элемента.

Бинарный поиск применяется к отсортированным множествам и заключается в последовательном разбиении множества пополам и поиска элемента только в одной половине на каждой итерации.

Таким образом, идея этого метода заключается в следующем. Поиск нужного значения среди элементов упорядоченного массива (по возрастанию или по убыванию) начинается с определения значения центрального элемента этого массива. Значение данного элемента сравнивается с искомым значением и в зависимости от результатов сравнения предпринимаются определенные действия. Если искомое и центральное значения оказываются равны, то поиск завершается успешно. Если искомое значение меньше центрального или больше, то формируется массив, состоящий из элементов, находящихся слева или справа от центрального соответственно. Затем поиск повторяется в новом массиве ( рис. 37.1).

Алгоритм бинарного поиска

Шаг 1. Определить номер среднего элемента массива middle=(high+low)/2.

Шаг 2. Если значение среднего элемента массива равно искомому, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу.

Шаг 3. Если искомое значение больше значения среднего элемента, то возьмем в качестве массива все элементы справа от среднего, иначе возьмем в качестве массива все элементы слева от среднего (в зависимости от характера упорядоченности). Перейдем к Шагу 1.

В массиве может встречаться несколько элементов со значениями, равными ключу. Данный алгоритм находит первый совпавший с ключом элемент, который в порядке следования в массиве может быть ни первым, ни последним среди равных ключу. Например, в массиве чисел 1, 5, 5, 5, 5, 5, 5, 7, 8 с ключом key =5 совпадет элемент с порядковым номером 4, который не относится ни к первому, ни к последнему.

Существуют две модификации рассматриваемого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент: округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором - к правой.

Рис. 37.1. Демонстрация алгоритма бинарного поиска

//описание функции бинарного поиска

int BinarySearch(int *x, int k, int key){

bool found = false;

int high = k - 1, low = 0;

int middle = (high + low) / 2;

while ( !found && high >= low ){

if (key == x[middle])

found = true;

else if (key < x[middle])

high = middle - 1;

else

low = middle + 1;

middle = (high + low) / 2;

}

return found ? middle : -1 ;

}

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

Время выполнения алгоритма бинарного поиска: если функция имеет вещественный аргумент, найти решение с точностью до можно за время , а если аргумент дискретен, то поиск решения займет 1 + log n времени.

Достоинством данного алгоритма является относительная быстрота выполнения поиска, по сравнению с алгоритмом последовательного поиска. Недостаток заключается в том, что бинарный поиск может применяться только на упорядоченном множестве.

Ключевые термины

Бинарный (двоичный, дихотомический) поиск - это поиск заданного элемента на упорядоченном множестве, осуществляемый путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей.

Ключ поиска - это поле записи, по значению которого происходит поиск

Поиск - это процесс нахождения конкретной информации в ранее созданном множестве данных.

Поиск с барьером - это модификация алгоритма последовательного поиска, ускоряющая процесс путем определения граничного элемента.

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

алгоритм последовательный бинарный поиск

Краткие итоги

1. Одним из важнейших действий со структурированной информацией является поиск.

2. Существует множество различных алгоритмов поиска, которые принципиально зависят от способа организации данных. У каждого алгоритма поиска есть свои преимущества и недостатки.

3. Последовательный (линейный) поиск является простейшим видом поиска заданного элемента на некотором множестве, осуществляемым путем последовательного сравнения очередного рассматриваемого значения с искомым до тех пор, пока эти значения не совпадут.

4. Существует модификация алгоритма последовательного поиска, которая ускоряет поиск путем установки в рассматриваемом множестве барьера.

5. Бинарный (двоичный, дихотомический) поиск является поиском заданного элемента на упорядоченном множестве, осуществляемым путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Бинарный поиск применяется к отсортированным множествам.

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

Размещено на Allbest.ru

...

Подобные документы

  • Основные определения поиска подстроки в строке. Простейшие алгоритмы поиска подстроки в строке. Алгоритмы последовательного поиска и Рабина-Карпа, создание и описание программы, реализующей их. Порядок работы с приложением. Тестирование алгоритмов.

    курсовая работа [2,7 M], добавлен 24.05.2012

  • Теоретические сведения об алгоритмах поиска подстроки в строке. Глобализация информации в сети Internet. Интеллектуальный поиск. Алгоритм последовательного (прямого) поиска, Рабина и их применение. Анализ алгоритмов. Реализация программного кода.

    курсовая работа [230,8 K], добавлен 12.02.2009

  • Теоретические сведения. Основные понятия. Строка, её длина, подстрока. Понятие о сложности алгоритма. Алгоритмы основанные на методе последовательного поиска. Алгоритмы Рабина, Кнута - Морриса - Пратта, Бойера – Мура.

    курсовая работа [138,3 K], добавлен 13.06.2007

  • Задача об оптимальном графе для децентрализованного поиска. Жадный алгоритм. Модель Клайнберга. Математическая модель. Алгоритмы решения. Алгоритм локального поиска. Табу алгоритм. Метод ветвей и границ. Выбор между одинаковыми соседями. Стартовый граф.

    дипломная работа [4,1 M], добавлен 23.10.2016

  • Разработка программы на языке С#, которая будет заниматься построением бинарного дерева для исходных данных и их редактированием, поиском информации о товарах по заданному ключу. Графические схемы алгоритмов поиска и удаления элемента бинарного дерева.

    курсовая работа [796,9 K], добавлен 22.02.2016

  • Программа последовательного поиска в последовательном неотсортированном массиве реквизитов единственного значения. Алгоритм сортировки простым выбором. Программа индексирования основного файла по одному реквизиту. Индексные файлы по реквизитам.

    лабораторная работа [896,4 K], добавлен 15.02.2009

  • Организация возможности просмотра текстовых файлов и осуществления поиска нужных слов в тексте. Редактирование текста (шрифт, размер). Алгоритм поиска подстроки в строке (метод Кнута-Морриса-Пратта). Загрузка текста из файла (с расширением .txt).

    курсовая работа [2,2 M], добавлен 29.05.2013

  • Общая характеристика организации массива в виде двоичного дерева. Особенности линейного и двоичного поиска заданного элемента массива. Методика упорядочения массива методом сортировки деревом. Инструкции и текст программы для нечисленной обработки данных.

    курсовая работа [242,3 K], добавлен 12.11.2010

  • Описание алгоритма сортировки с двоичным включением, выбор структур данных. Пример сортировки массива, отсортированного случайным образом. Алгоритм покрытия по методу "Построение одного кратчайшего покрытия". Волновой алгоритм поиска длиннейшего пути.

    курсовая работа [78,2 K], добавлен 24.09.2010

  • Алгоритмы и алфавит языка Турбо Паскаль. Основные типы данных. Операторы присваивания, перехода и выбора. Понятие массива в Паскале. Особенности работы со строками в программе. Использование линейного поиска и поиска с барьером. Основные виды сортировок.

    учебное пособие [53,2 K], добавлен 09.11.2009

  • Понятие алгоритма как набора инструкций, описывающего порядок действий. Поиск в ширину - метод обхода графа и поиска пути в нем. Пример работы алгоритма поиска в ширину, его неформальное и формальное описание. Реализация с помощью структуры "очередь".

    курсовая работа [684,8 K], добавлен 05.04.2015

  • Характеристика структурированного языка программирования С, его основных структурных компонентов, области памяти, библиотеки. Методы поиска в массивах данных. Описание программы, функции сортировки и меню выбора, последовательного и бинарного поиска.

    курсовая работа [1,7 M], добавлен 19.05.2014

  • Методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня. Программирование алгоритмов сортировки и поиска в рамках создаваемого программного средства на языке Delphi. Создание руководства пользователя.

    курсовая работа [1,7 M], добавлен 16.04.2012

  • Эвристические и теоретические методы прямого поиска. Алгоритм поиска значения по симплексу и по образцу. Основная идея метода сопряженных направлений Пауэлла. Ознакомление с преимуществами и недостатками методов безусловной многопараметровой оптимизации.

    презентация [862,9 K], добавлен 30.10.2013

  • Способы построения остовного дерева (алгоритма поиска в глубину и поиска в ширину). Вид неориентированного графа. Понятие и алгоритмы нахождения минимальных остовных деревьев. Последовательность построения дерева графов по алгоритмам Крускала и Прима.

    презентация [22,8 K], добавлен 16.09.2013

  • Транскрипционные факторы. Представление регуляторных элементов. Алгоритмы поиска мотивов. Скрытые Марковские модели и вспомогательные алгоритмы. Тестирование на сгенерированных и реальных данных, отличия в показателях. Сравнение с другими алгоритмами.

    дипломная работа [5,0 M], добавлен 24.05.2012

  • Алгоритм добавления нового элемента в дерево и поиска по нему. Порядок разработки руководства пользователя. Принцип работы с экранным меню. Методика и этапы добавления нового элемента. Формирование и содержание инструкции системного программиста.

    курсовая работа [411,8 K], добавлен 06.06.2014

  • Основные критерии и требования к средствам поиска по ресурсу. Технологии создания инструментов поиска. Способы поиска по ресурсу. Принцип действия поиска по ключевым словам и при помощи поисковых систем. Разработка ресурса "Поиск по ресурсу" в виде блога.

    курсовая работа [983,7 K], добавлен 01.02.2015

  • Классы задач P и NP, их сводимость. Примеры NP-полных и NP-трудных задач. Сущность метода поиска с возвратом. Алгоритмы решения классических задач комбинаторного поиска. Решение задачи о восьми ферзях. Поиск оптимального решения методом ветвей и границ.

    презентация [441,5 K], добавлен 19.10.2014

  • Обоснование выбора языка и среды программирования. Обзор и анализ существующих программных решений. Разработка графического и пользовательского интерфейса. Алгоритм бинарного поиска. Методы добавления, удаления элемента из дерева и вывода на экран.

    курсовая работа [1,3 M], добавлен 31.05.2016

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.