Общая классификация алгоритмов поиска

· Все методы можно разделить на статические и динамические. При статическом поиске массив значений не меняется во время работы алгоритма. Во время динамического поиска массив может перестраиваться или изменять размерность.

· Так же методы поиска можно разделить на методы, использующие истинные ключи и на методы, работающие по преобразованным ключам. В данном случае "ключем" называют то значение, которое мы ищем.

· методы основанные на сравнении самих значенийи методы, основанные на ихцифровых свойствах. Так называемые методы хэширования.

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

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

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

Элемент найден, т. е. а[i ]= x.

Весь массив просмотрен и совпадения не обнаружено.

Это дает нам линейный алгоритм:

Алгоритм 1.

i:=0;

while (i<N) and (а[i]<>х) do i:=i+1

Следует обратить внимание, что если элемент найден, то он найден вместе с минимально возможным индексом, т. е. это первый из таких элементов. Равенство i=N свидетельствует, что совпадения не существует.

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

На каждом шаге алгоритма осуществляется увеличение индекса и вычисление логического выражения. Можно упростить шаг алгоритма, если упростить логическое выражение, которое состоит из двух членов. Это упрощение осуществляется путем формулирования логического выражения из одного члена, но при этом необходимо гарантировать, что совпадение произойдет всегда. Для этого достаточно в конец массива поместить дополнительный элемент со значением x. Такой вспомогательный элемент называется барьером. Теперь массив будет описан так:

а: array[0..N] of integer

и алгоритм линейного поиска с барьером выглядит следующим образом:

Алгоритм 2.

a[N]:=x; i:=0;

while a[i]<>x do i:=i+1

Ясно, что равенство i=N свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.