Претраживање низа

Проблем претраживања знатно је једноставнији од проблема сортирања. Циљ претраживања низа је пронаћи на којој позицији се налази елемент који поседује неко својство. На пример, често је потребно пронаћи где се налази елемент који је једнак некој фиксној вредности која се обично назива кључ претраге. Најједноставнији начин претраге назива се линеарно или секвенцијално претраживање, с обзиром да се елементи низа претражују „линијски“, елемент по елемент. Обилази се цео низ, и сваки елеменат се упоређује са траженом вредношћу. Излазак из циклуса наступа кад прођемо ЦЕО низ или кад наиђемо на тражени елеменат.

Постоји неколико варијанти овог алгоритма:

1. само одређује да ли постоји тражени елеменат или не, користи се за неуређене низове:

for(i=0;i<n&&a[i]!=b;i++);
return i<n;

2. само одређује да ли постоји тражени елеменат или не, користи се за уређене низове:

for(i=0;i<n&&a[i]<b;i++);
return i<n&&a[i]==b;

3. одређује редни број траженог елемента:

if(n>0)
kraj=0;i=0;}
else
{kraj=1;nadjen=0;}
while (!kraj)
{
if(a[i]==b)
{kraj=1;nadjen=1;br=i;}
else {if(a[i]<b)
{kraj=1;nadjen=0;}
i++;
}
}
if (nadjen) printf(„%d”,br);
else printf („nema”);

Бинарно претраживање

У случају да је низ који се претражује претходно сортиран (нпр. у растући поредак), претрага се може обавити знатно брже, поступком познатим под именом бинарно претраживање. Вредност коју тражимо прво треба тражити у средини низа. У случају да је елемент у средини низа већи од траженог елемента, можемо одмах знати да се тражени елемент може налазити само у првој половини низа, с обзиром да је низ сортиран у растући поредак. Слично, у случају да је елемент у средини низа мањи од траженог елемента, он се може налазити само у другој половини низа. Тако, у следећем кораку можемо величину низа редуковати на половину, и понављати исти поступак све док не буде успешна претрага, или док се величина низа не сведе на један елемент.

donja=1;gornja=n;nadjen=0;
 while(donja<=gornja&&!nadjen)
 {
 sredina=(donja+gornja)/2;
 if(b=a[sredina])nadjen=1;
 else if(b<a[sredina])gornja=sredina-1;
 else donja=sredina+1;
 }
 if(!nadjen)binpret=0;
 else binpret=sredina;
 if(!binpret)printf(„%d”,binpret);

Дефинисати функције за претраживање низа: секвенцијално за несортиран и сортиран низ и бинарно претраживање. Дефинисати функције за сортирање реалних низова по неопадајућем редоследу: метод селекције и метод селекције – побољшана верзија. Предвидети приказивање делимично сортираног низа после сваког проласка кроз циклус. У главном програму унети реалан низ. Након уношења броја за претрагу изабрати тип претраживања. Ако изабрани тип претраживања захтева сортирани низ – изабрати жељени тип сортирања. Приказати сортирани низ и редни број траженог елемента.

#include<stdio.h>
 int sekvencijalno1(float a[], int n, float b)
 {
 int i,br,nadjen=0;
 for (i=0;i<n;i++)if (a[i]==b) {br=i;nadjen=1;}
 if(nadjen)return br;
 else return br=-1;
 }
 int sekvencijalno2(float a[], int n, float b)
 {
 int kraj,i,nadjen,br;
 if(n>0)
 { kraj=0;i=0;}
 else
 {kraj=1;nadjen=0;}
while(!kraj)
 {
 if(a[i]==b)
 {kraj=1;nadjen=1;br=i;}
 else
 if(a[i]>b)
 {kraj=1;nadjen=0;}
 i++;
 }
 if(nadjen)return br;
 else return br=-1;
 }
int binarno(float a[], int n, float b)
 {
 int donja=0,gornja=n-1,nadjen=0,sredina;
 while(donja<=gornja&&!nadjen)
 {
 sredina=(donja+gornja)/2;
 if(b==a[sredina])nadjen=1;
 else if(b<a[sredina]) gornja=sredina-1;
 else donja=sredina+1;
 }
 if(nadjen)return sredina;
 else return sredina=-1;
 }
 void razmeni(float *x,float *y)
 {
 float p;
 p=*x;*x=*y;*y=p;
 }
void izbor1(float a[],int n)
 {
 int i,j,k;
 float p;
 for(i=0;i<n-1;i++)
 {
 for(j=i+1;j<n;j++) if(a[j]<a[i]) razmeni(&a[i],&a[j]);
 for(k=0;k<n;printf("%.2f ",a[k++]));printf("\n");
 }
}
void izbor2(float a[],int n)
 {
 int i,j,m,k;
 float p;
 for(i=0;i<n-1;i++)
 {
 m=i;
 for(j=i+1;j<n;j++) if(a[j]<a[m]) m=j;
 if (m!=i) razmeni(&a[i],&a[m]);
 for(k=0;k<n;printf("%.2f ",a[k++]));printf("\n");
}
 }
 main()
 {
 float a[20], b;
 int n, i, c, rezultat, m;
 while(1)
 {
 printf("unesi broj elemenata niza: ");
 scanf("%d",&n);if (n<=0)break;
 printf("\nunesi elemente niza:\n");
 for(i=0;i<n;i++){printf("%d.",i+1);scanf("%f",&a[i]);}
 printf("\nunesi trazeni elemenat: ");scanf("%f",&b);
 printf("\nunesi metodu pretrazivanja:\n");
 printf("1 - sekvencijalno (za nesortiran niz)\n");
 printf("2 - sekvencijalno (za sortiran niz)\n");
 printf("3 - binarno\n");scanf("%d",&c);
 switch(c)
 {
 case 1: rezultat=sekvencijalno1(a,n,b);
 if (rezultat==-1)printf("\nbroj nije pronadjen\n");
 else printf("trazeni broj %.2f nalazi se na %d mestu\n",b,rezultat+1);break;
case 2:printf("\nizabrani nacin pretrazivanja zahteva sortiran niz. Unesite nacin sortiranja\n");
 printf("\n1 - metoda selekcije");
 printf("\n2 - metoda selekcije - poboljsana");
 scanf("%d",&m);
 printf("\n");
 switch(m)
 {
 case 1:izbor1(a,n);break;
 case 2:izbor2(a,n);break;
 default:printf("greska\n");
 }
 printf("sortiran niz:\n");
 for(i=0;i<n;printf("%.2f ",a[i++]));printf("\n");
 rezultat=sekvencijalno2(a,n,b);
 if (rezultat==-1)printf("\nbroj nije pronadjen\n");
 else printf("trazeni broj %.2f nalazi se na %d mestu\n",b,rezultat+1);break;
case 3:printf("\nizabrani nacin pretrazivanja zahteva sortiran niz. Unesite nacin sortiranja\n");
 printf("\n1 - metoda selekcije");
 printf("\n2 - metoda selekcije - poboljsana");
 scanf("%d",&m);
 printf("\n");
 switch(m)
 {
 case 1:izbor1(a,n);break;
 case 2:izbor2(a,n);break;
 default:printf("greska\n");
 }
 printf("sortiran niz:\n");
 for(i=0;i<n;printf("%.2f ",a[i++]));printf("\n");
 rezultat=sekvencijalno2(a,n,b);
 if (rezultat==-1)printf("\nbroj nije pronadjen\n");
 else printf("trazeni broj %.2f nalazi se na %d mestu\n",b,rezultat+1);break;
default:printf("\n*** greska ***\n");
 }
 }
 }
Advertisements

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се / Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се / Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се / Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се / Промени )

Повезивање са %s