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

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

Задача поиска. Пусть заданы линейные списки: список элементов В=< К1, К2, К3,..., Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация, когда V содержит один элемент, а в В имеется не более одного такого элемента.

Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi – относительная частота использования элемента Кi в В, а Si – количество сравнений, необходимое для его поиска, то

n Max{А} = max{ Si, i=1, n }; Avg{А} = Pi Si. i=1

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

Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, поместив часто встречаемые элементы в начало списка.

 

Пример 15.7

Пусть во входном потоке задано 5 целых чисел К1, К2,... К5 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке. Без использования стоппера программа может быть реализована следующим образом:

#include < stdio.h>

void main(void)

{

int k[5], v, i, count=0;

puts(“Vvedite elementi: ”);

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

scanf(“%d”, & k[i]);

puts(“vvedite element dlja poiska”);

scanf(“%d”, & v);

i=0;

while(i< 5)

{ if (k[i]==v)

{

printf(“element-%d position-%d\n”, v, (i+1));

count++;

}

i++;

}

if(count==0) printf(“element-%d ne naiden “, v);

}

6.2. Поиск элемента по индексу

Пример 15.8

#include < stdio.h>

void main(void)

{ int k[5], v, i, count=0;

puts(" Vvedite elementi: ");

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

scanf(" %d", & k[i]);

puts(" vvedite element dlja poiska");

scanf(" %d", & v);

i=0;

while(i< 5)

{

if (k[i]==v)

{

printf(" element-%d position-%d\n", v, (i+1));

count++;

}

i++;

}

if(count==0) printf(" element-%d ne naiden ", v);

puts(" Vvedite index elementa");

scanf(" %d", & v);

if(v> =0& & v< 5)

printf(" element s indexom %d raven = %d\n", v, k[v]);

else printf(" Elementa s takim indexom net\n");

}

Анализ линейного поиска

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

 

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

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

Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска равен log2(N), и при одинаковой частоте использования каждого элемента Avg бинарного поиска равен log2(N). Недостаток бинарного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов.

 

Пример 15.9

#include < stdio.h>

void main()

{

int k[6];

int v, i, j, m;

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

scanf(" %d", & k[i]);

scanf(" %d", & v);

i=0;

j=6;

m=3;

while (k[m]! =v)

{

if (k[m] < v)

i+=m;

else j=m-i;

m=(i+j)/2;

}

printf(" %d %d", v, m);

}

 

Варианты индивидуальных заданий

Разработать программу для создания пяти динамических массивов: a[ ], b[ ], c[ ], d[ ] и e[ ]. Эти массивы необходимо отсортировать соответственно методом обмена, методом выбора, методом вставки, методом Шелла и методом Хоора. Организовать последовательный поиск определенного элемента в каждом исходном массиве и подсчитать количество совпадений этого элемента в каждом массиве. Организовать бинарный поиск определенного элемента в каждом отсортированном массиве. Разработать в программе меню, структура которого следующая:

Menu:

1. Initilization arrays (инициализация массивов)

2. Result of bubble sort

3. Result of min sort

4. Result of insert sort

5. Result of Shell sort

6. Result of Hoor sort

7. Poisk

7.1. Posledovatel’nyi poisk

7.2. Binarnyi poik

Результаты всех сортировок и поиска записать в файл.