Задача поиска. Алгоритмы линейного поиска.

Общая постановка. В заданной совокупности элементов требуется найти элемент, обладающий заданным набором свойств.

Важнейший частный случай. Задан массив x, нужно определить имеет ли в нем элемент, совпадающий с заданным числом a. Если такой элемент обнаружен, то в качестве дополнительной информации следует получить номер совпадающего с заданным элемента массива

a) Классический алгоритм

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

б) Быстрый алгоритм

Идея быстрого алгоритма состоит в том, что выражения flag и x[i]=a эквивалентны. Следовательно, в условии в заголовке цикла вместо not flag можно использовать x[i]<>a, и отказаться от использования индикатора flag.

в) Алгоритм с барьером

Следующее улучшение состоит в упрощении условия в заголовке цикла. Целевым является условие x[i]<>a, которое убрать или упростить невозможно. Следовательно, можно рассматривать только условие i<=N, обеспечивающие прекращение просмотра после исчерпания всех элементов цикла. Идея состоит в выставлении в конце массива «барьера». Для этого в массив добавляется N+1 элемент, значение которого приравнивается к искомому.

В алгоритмах линейного поиска максимальное количество операций, которое приходится проделать для определения результата поиска пропорционально N.

 

Бинарный поиск.

Если данные упорядочены, то поиск можно сделать значительно более эффективным. Если x[i]<=x[i+1],  i=1,2,…,N-1, то массив называется упорядоченным (отсортированным) по возрастанию.

Искомый элемент сравнивается со средним элементом массива.

Если они совпадают, то задача уже решена. Так как массив упорядочен, то при не совпадении элементов, в дальнейшем поиске можно не рассматривать одну из половин массива.

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

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

Итак, во время поиска приходится повторять следующие действия: 1) выбирать средний элемент массива; 2) сравнивать его с искомым; 3) при необходимости уменьшать рассматриваемую часть массива в два раза выбором его правой или левой половины.

Так как начальный и конечный элементы рассматриваемой части массива при отбрасывании одной из половин массива будут изменяться, то для записи алгоритма следует использовать переменные, имеющие смысл номеров начального (левого) L и конечного (правого) R элементов массива. Поскольку в начале рассматривается весь массив, то L=1, а R=N. Номер среднего элемента M можно найти стандартным способом: M=(R+L) div 2.

Оценим максимальное количество операций, которые потребуется выполнить для решения задачи поиска в алгоритме бинарного поиска.

На первом шаге количество K рассматриваемых элементов массива равно N

После первого шага количество K рассматриваемых элементов массива уменьшается в два раза K=N/2.

После второго шага - в четыре раза

Вообще, после шага с номером m:

В худшем случае процесс поиска закончится после того, как останется один элемент: . Отсюда:

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

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: