1. Задачи поиска

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

Предположим, что о расположении данных в таблице нет никаких сведений. Тогда проверка одного элемента не дает никакой информации об остальных. Самый разумный способ поиска в этом случае — последовательный перебор:

алг поиск (арг цел N, арг вещ таб a[1: N], арг вещ х, рез цел k)

нач

k:=1

нц пока k<=N и_ a[k]<>x

k:=k+1

кц

если k>N

то k:=0

все

кон

Алгоритм поиска объекта во множестве, состоящем из n объектов, последовательно перебирает объекты множества.

Сложность худшего случая равна n (искомый объект может оказаться последним); средняя продолжительность поиска равна сумме всех номеров от 1 до n, деленной на n, что составляет (n+1)/2. В обоих случаях функция сложности имеет вид a*n+b, т. е. является линейной.

2.Поиск максимального элемента

Дано n чисел. Требует­ся найти в этой последовательности максимальное число. Алгоритм метода решения сформулируем в следующем виде:

1.         в некоторой памяти М запоминаем первое число;

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

3.         повторяем второй шаг до конца данной последовательности.

Сложность приведенного алгоритма также линейна (каж­дое из и чисел просматривается только один раз, и при этом совершается не более пяти операций).

3.Упорядочение последовательности

С помощью предыдущего алгоритма можно построить алгоритм упорядоче­ния последовательности чисел. Для этого найдем наибольшее число в исходной последовательности из n чисел, вы­ пишем его и удалим из последовательности. Далее опреде­лим наибольшее число в оставшейся последовательности из n-1 чисел, припишем его справа к найденному ранее числу и вычеркнем из исходной последовательности и т. д. Трудо­емкость этого алгоритма равна многочлену второй степени.

4.Поиск в упорядоченной последовательности

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

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

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

Ниже приведен фрагмент реализации бинарного поиска элемента X в таблице a[1:N):

нач

L:=l {на первом шаге рассматривается весь массив}

R:=N

F:= О {признак результативности поиска: F=l, если X найден, и 0 —в противном случае}
нц пока L<=R и F=0 {условия продолжения поиска}

М:= div (L+R, 2) {выбор среднего элемента}

если А[М}=Х

то F:=l {элемент найден, поиск надо прекратить}

иначе если А[М]<Х

то L:=M+i {отбрасывается левая часть}

иначе R:=M-i {отбрасывается правая часть}

все

все

кц

кон

Поскольку на каждом шаге длина последовательности, в которой происходит поиск, уменьшается вдвое, общая трудо­емкость этого алгоритма имеет порядок Log2 x*п.

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

Так мы ищем слова в словарях, книги в каталогах, телефоны в справочниках и т. д.