15.2 Приемы реализации линейного поиска

Поиск элемента неупорядоченного массива равного заданному значению – классическая задача поиска, общий алгоритм представлен на рис.15.2.

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

print_linear_seach(int* k, int N)

{

i=0;

while(k[i]!=v && i<N) i++;//перебор элементов

if (k[i]==v) printf("%d %d",v,i);

else printf("%d не найден",v);

}

Чтобы не проверять каждый раз в цикле условие достижения границы массива можно установить барьер (стоппер) для ограничения изменение индекса. В качестве барьера можно установить искомое значение, которое следует добавить в конец массива. Достоинством такого решения является уменьшение одной проверки в цикле. Выход из цикла, в котором теперь остается только одно условие поиска, может произойти либо на найденном элементе, либо на барьере.

print_linear_seach(int* k, int N)

{

intk[N+1],v,i;

...

k[N]=v; /* установка стоппера */

i=0;

while(k[i]!=v) i++;

if (i<N) printf ("%d %d",v,i);

else printf ("%d не найден",v); }

Приведенные выше функции позволяют найти первое вхождение искомого значения в массиве, если необходимо найти последнее, то следует построить цикл так:

int j=-1;

for(i=0; i<N; i++)if(a[i]==K) j=i;

if (j==-1) puts("искомый элемент не найден");

else printf("Найден элемент %d/n", j);

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

print_linear_seach(int* k, int N)

{

inti;

// Задание значений K и чтение массива

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

if(a[i]==K) printf("Найден элемент %d/n", i);

if (i==N) puts("искомый элемент не найден");

return;

}

15.3 Примеры реализации алгоритмов поиска

Пример 1.Поиск расстояния между минимальным и максимальным элементом массива.

int dist (double *a, int n)

{

imin=0;// для хранения индекса миним. элемента

imax=0;//для хранения индекса макс. элемента

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

{

if(a[i]<a[imin] imin=i;

if(a[i]>a[imax] imax=i;

}

return abs(imin-imax);

}

Поиск не самого значения минимума или максимума, а индекса минимального (максимального) элемента эффективнее, так как уменьшает число присваиваний, при естественном хранении искомого элемента в исходном массиве.

Пример 2. Программа вычисления суммы элементов массива, начиная с первого отрицательного элемента.

#include <stdio.h>

#include <locale.h>

int main()

{

int Arr[100];

int i, n, Sum;

setlocale(0,"Russian");

printf("Введите количество элементов в массиве - ");

scanf("%d", &n);

if(n>100) {puts(“Много элементов”);return -1;}

/*чтение элементов*/

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

{

printf("№%d - ",i+1);

scanf("%d", (Arr+i));

}

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

if (Arr[i] <0) break;

if(i==n) { puts(“Отрицательный элемент не найден”);return -1;}

for (Sum=0, i < n; Sum+ = Arr[i++]);

printf("Сумма - %d\n", Sum);

system("pause");

return 0;

}

Пример3. Поиск минимального элемента упорядоченного массива равного заданному значению

main()

{