Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,...,Кn> и список ключей V= (в простейшем случае это целые числа). Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация когда V содержит один элемент, а в В имеется не более одного такого элемента. Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi — относительная частота использования элемента Кi в В, а Si — количество сравнений, необходимое для его поиска, то
Max{А} = max{ Si, i=1,n } ; Avg{А} = Pi Si . i=1
Последовательный поиск предусматривает последовательный просмотр всех элементов списка В в порядке их расположения, пока не найдется элемент равный V. Если достоверно неизвестно, что такой элемент имеется в списке, то необходимо следить за тем, чтобы поиск не вышел за пределы списка, что достигается использованием стоппера. Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элю5ента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка.
Пусть во входном потоке задано 100 целых чисел К1,К2,... К100 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке. Без использования стоппера программа может быть реализована следующим образом:
/*    последовательный поиск без стоппера    */
#include
main()
{
  int k[100],v,i;
  for (i=0;i<100;i++)
  scanf("%d",&k[i]);
  scanf("%d",&v);
  i=0;
  while(k[i]!=v && i<100) i++;
  if (k[i]==v) printf("%d %d",v,i);
  else printf("%d не найден",v);
}
С использованием стоппера программу можно записать в виде:
/*  последовательный поиск со стоппером    */
#include
main()
{
  int k[101],v,i;
  for (i=0;i<100;i++)
  scanf("%d",&k[i]);    /*   ввод данных  */
  scanf("%d",&v);
  k[100]=v;    /*   стоппер      */
  i=0;
  while(k[i]!=v) i++;
  if (i<100) printf ("%d %d",v,i);
  else printf ("%d не найден",v);
}
Приведенная ниже Функция осуществляет поиск в массиве символов известной длины, пока не будет найден элемент с заданным ключом:
/*  Последовательный поиск  */
int  sequential_search(char  *items,  int count,  char key)
{
register  int  t;
for(t=0;  t  <  count;  ++t)
if(key  ==   items[t]}  return t; return  -1;  /*  ключ  не  найден   */
}
Здесь items — указатель на массив, содержащий информацию. Функция возвращает индекс подходящего элемента, если таковой существует, либо -1 в противном случае.