Примерами
поисковых задач могут служить поиск первого отрицательного, первого положительного и любого первого элемента, отвечающего некоторому условию, поиск единственного элемента, равного некоторому конкретному значению. Особенность задач этого класса в том, что нет необходимости просматривать весь
массив. Просмотр нужно закончить сразу, как только требуемый элемент будет найден. При этом может производиться как поэлементный просмотр, так и выборочная обработка массива. Однако, в худшем случае, для поиска элемента требуется просмотреть весь массив. Такой тип поиска называется линейным. Если массив не очень большой, затраты времени линейного поиска не столь заметны. Но при солидных объемах информации время поиска становится серьезным показателем. Поэтому существуют методы, позволяющие уменьшить время поиска: поиск с барьером и двоичный поиск. Чаще всего при программировании поисковых задач используются циклы с предусловием или постусловием, в которых условие выхода формируется из двух условий. Одно условие — пока искомый элемент не найден, а второе — пока есть элементы массива. После выхода из цикла осуществляется проверка: по какому из 2-х условий произошел выход.
Пример 1
Дан массив А вещественных чисел. Определить первый отрицательный элемент массива и его номер.
Рис. 1. Классический алгоритм поиска
int otr1(float a[], int n) /* функция ищет в массиве первый отрицательный элемент
и возвращвет его индекс. Если это значение равно -1, то
отрицательный элемент не найден */
{ float potr;
int i,iotr=-1,key;
i=0;
key=0;
while((key==0)&&(i<n))
if(a[i]<0)
{key=1;
potr=a[i];
iotr=i;
}
else i++;
printf("potr= %6.2f iotr= %4d\n",potr,iotr);
return iotr;
}
Другой вариант этой функции.
int otr2(float a[], int n) /* функция ищет в массиве первый отрицательный элемент
и возвращвет его индекс. Если этот индекс равен n,
то отрицательный элемент не найден */
{
int i;
i=0;
while(i<n))
if(a[i]<0)
{
printf("potr= %6.2f iotr= %4d\n",a[i],i);
return i;
}
else i++;
return i;
}