Технологии Программирования. 7 лекция

Тема 5: Алгоритмы поиска

Задача поиска – это поиск заданного элемента в массиве. Алгоритмы поиска можно разбить на группы, то есть классифицировать.

1. КЛАССИФИКАЦИЯ

1 вариант классификации

Все методы поиска можно разделить на:

•статические и

•динамические.

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

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

Например,

1)Поиск слова в словаре.

Как бы Вы его не искали, Ваш алгоритм обязательно будет статическим, таккак сам словарь (массив слов) не будет изменяться во время поиска. Если конечно не выдирать из него страницы.

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

2 вариант классификации

Методы поиска можно разделить на

•методы, использующие истинные ключи и

•методы, работающие по преобразованным ключам.

Вданном случае "ключем" называют то значение, которое мы ищем.

Например,

1)поиск в колоде карт - поиск по истинным ключам, то есть имеете дело с тем, что есть.

2)Поиск в словаре - поиск по преобразованным ключам, так как все слова отсортированы в алфавитном порядке, то есть массив значений изменен перед началом поиска.

3 вариант классификации –

•методы, основанные на сравнении самих значений и

•методы, основанные на их цифровых свойствах

(методы хэширования)

Пример, необходимо найти определенную карту в колоде.

нестандартный способ -придумали такую функцию, которая вычисляет номер нужной карты в колоде.

Например

f("крестовая дама") = 5 , а f("туз пик")=12

То есть, подставив в функцию искомое значение, мы получаем местоположение этого значения в нашем массиве.

Это же самый что ни на есть ПРЯМОЙ доступ, по сравнению с ПОСЛЕДОВАТЕЛЬНЫМ перебором всех ( или некоторых ) значений в искомом массиве.

Этот метод и называется методом хэширования.

Главная проблема – найти функцию f(К), которая должна определять ОДНОЗНАЧНОЕ соответствие для каждого значения в массиве.

Находить подобные функции довольно сложно

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

Название метода раскрывает суть алгоритма – необходимо запустить цикл повторений, который будет просматривать все элементы один за другим до тех пор, пока нужный элемент не будет найден,

либо не будут пройдены все элементы

Прямой перебор всех значений прост в понимании, легок в исполнении и достаточно быстр на малых массивах данных.

Метод прямого перебора оптимален для малых массивов.

Кодпрограммы – две функции

1 функция

int Search(int A[], int size, int n)

{

int i=0; while( i!=n )

{ /* если элемент массива с индексом I равен искомому, то функция возвращает его номер,

в противном случае возвращает -1

*/

if (A[i] = = n) return i; else i++;

return -1;

}

2 функция main()

{

int i, size,

int A[100], n, p, k;

// вводим с клавиатуры cin>>size; // размер массива

for(k=0;k<size;k++) cin>>A[k]; // элементы массива

//вводим элемент для поиска cin>>n;

//осуществляем поиск p=Search(A,size,n);

//выводим результат поиска

if( p = = -1) cout<<”No”;

else cjut<<”Yes” << (++p);

…

}

3. Двоичный поиск (Бинарный)

Бинарный поиск впервые упомянут Джоном Мочли в 1946г.

Этот метод применим к отсортированным по возрастанию массивам.

Метод называется двоичным, потому что после каждой операции количество просматриваемых значений уменьшается в 2 раза.