Algoritmy vyhľadávania

Vyhľadávanie

Vyhľadávanie je základnou úlohou pri práci s väčším objemom dát. Podľa povahy dát (zložitosti, usporiadania, veľkosti) volíme vhodný algoritmus vyhľadávania. Algortimy vyhľadávanie môžeme rozdeliť do niekoľko skupín:

1. Sekvenčné vyhľadávanie
2. Vyhľadávanie v usporiadaných zoznamoch (resp. poliach)
3. Vyhľadávanie v rekurzívnych štruktúrach

Sekvenčné vyhľadávanie

Jednoduché sekvenčné vyhľadávanie

Princíp tohto vyhľadávania je jednoduchý. Majme pole údajov o dĺžke n, v ktorých budeme hľadať údaj x. Pod pojmom údaj si môžeme ptredstaviť ľubovoľný dátový typ (celé číslo, reálne číslo, štruktúru, smerník na nejaký dátový typ). Princíp: postupne prechádzame pole od indexu 0 až po index n-1. V prípade, ak zistíme zhodu hľadaného prvku s prvkom v poli, tak funkciu ukončíme s úspechom, v opačnom prípade skončíme s výsledkom "prvok sa nenašiel"

Dohodnuté návratové hodnoty funkcie:

Vyhľadávacia funkcia bude vracať index prvku, ktorý je zhodný s hľadaným prvkom. V prípade neúspechu (hľadaný prvok sa v poli nevyskytuje) vráti funkcia hodnotu -1.

Názov funkcie	hladajSekvencne
Návratová hodnota	index nájdeného prvku (-1 pri neúspechu)
Parametre	pole prvkov - pole rozmer poľa - n hľadaný prvok - x
Zložitosť algoritmu	O(n)

1 int hladajSekvencne(int *pole,int dlzka,int x)
2 {  int i=0;
3 	while( (i<dlzka) && (pole[i]!=x) )
4 		 i++;
5     if(i<dlzka)  return i;
6 	else return -1;
7 }

Analýza riešenia: Algoritmus je vhodný pre vyhľadávanie údajov v dátovej štruktúre jednorozmerné pole. Údaje v tomto poli môžu byť neusporiadané. Podmienka i<dlzka zaručí, že sa bude prehľadávať len v rozsahu poľa pole. Vždy sa začína na indexe i=0; tento index sa postupne zvyšuje (i++), pokiaľ nenarazíme na hľadaný prvok (pole[i]!=x). Podmienka na riadku 5 je tam pre kontrolu prípadu, keď sme prešli celé pole a hľadaný prvok sme nenašli.

Nevýhoda: každý cyklus sa vykonávajú 2 porovnania: i<dlzka a pole[i]!=x

Jednoduché sekvenčné vyhľadávanie s nárazníkom

V predchádzajúcom prípade sa v každom cykle robili 2 porovnania. Určitými úpravami dokážeme tieto porovnania znížiť len na 1 porovnanie. Bude to však chcieť drobnú úpravu poľa, v ktorom budeme vyhľadávať. Pole si upravíme tak, že hľadaný prvok sa tam bude vždy vyskytovať. Skutočná veľkosť poľa pole musí byť teda o jednu položku väčšia ako je počet prvkov v poli. Iba po splnení tejto podmienky môžeme urobiť priradenie, ako je ukázané v riadku 3. Toto priradenie nazveme nárazník.

Názov funkcie	hladajSekvencneN
Návratová hodnota	index nájdeného prvku (-1 pri neúspechu)
Parametre	pole prvkov - pole rozmer poľa - n hľadaný prvok - x
Zložitosť algoritmu	O(n)

 1 int hladajSekvencneN(int *pole, int n, int x)
 2 {
 3   pole[n] = x; // musi byt na to vyhradene miesto!
 4   int i = 0;
 5   while (pole[i] != x) 
 6     i++;
 7   if (i < n) 
 8     return i;
 9   else
10     return -1;
11 }

Analýza riešenia: Algoritmus je vhodný pre vyhľadávanie údajov v dátovej štruktúre jednorozmerné pole. Údaje v tomto poli môžu byť neusporiadané. Priradenie pole[n] = x dovoľuje vynechať kontrolu i<dlzka (funkcia hladajSekvencne). Vieme, že prvok v poli vždy nájdeme, preto stačí na konci urobiť porovnanie (riadok 7), či sme prvok x našli na pozícii menšej ako n (v rozsahu poľa). Ak áno, vrátime hodnotu premennej i, čo je index nájdeného prvku, ak sme hľadaný prvok našli na pozícii n, vrátime hodnotu -1, pretože na pozícii n je náš nárazník.

Poznámka: Touto úpravou sme vylepšili čas, vyhľadávania, ale nie zložitosť algoritmu.

Nasledujúci obrázok ukazuje porovanie časov vyhľadávania doteraz spomínaných algorimnov pri opakovanom vyhľadávaní vo veľkých (cca 1 000 000 položiek) poliach. <pLines ymin=0 axiscolor=888888 cubic angle=90 plots legend xtitle=pocet_cisel ytitle=cas> ,hladajSekvencne,hladajSekvencneN 10 000, 0.016, 0.015 100 000, 0.235, 0.125 200 000, 0.859, 0.813 300 000, 1.281, 1.234 500 000, 2.156, 2.063 700 000, 3.031, 2.891 1 000 000, 4.328, 4.141 2 000 000, 8.656, 8.375 5 000 000, 21.531, 20.657 10 000 000, 42.422, 41.235 </pLines>

Vyhľadávanie v usporiadaných zoznamoch

Zložitosť O(n) pre algorimy lineárneho, resp. sekvenčného vyhľadávania dokážeme znížiť, ak sú údaje v ktorých budeme vyhľadávať usporiadané. V tomto prípade nemusíme pole prvkov v ktorom hľadáme prechádzať celé (od indexu 0 až po n-1), ale stačí si skontrolovať položky len na určitých miestach.

Binárne vyhľadávanie

Predpoklad správneho vyhľadávania je, že prvku sú v poli usporiadané. Postup vyhľadávania:

Použité premenné

• pole - jednorozmerné pole, v ktorom budeme vyhľadávať
• x - prvok, ktorý hľadáme
• n - veľkosť pola pole.
• lavy, pravy - rozsah poľa, (začiatok , koniec) kde budeme hľadať.

1. Rozdeľ pole na 2 polovice. Index stredného prvku vypočítaš ako:
   • stred=(lavy+pravy)/2
2. Ak platí lavy>pravy, tak koniec, prvok sa nenašiel.
3. Zober prvok v strede poľa (na indexe stred) a porovnaj ho s hľadaným prvkom x
4. Ak sa x zhoduje so stredným prvkom - koniec. Výsledok je index tohto prvku
5. V opačnom prípade
   • Ak je x väčšie ako stredný prvok, tak hľadaj v pravej časti poľa
     • lavy=stred+1, pravy zostava nezmenený (choď na krok 1)
   • Ak je x väčšie ako stredný prvok, tak hľadaj v ľavej časti poľa
     • lavy=zostava nezmenený, pravy = stred-1 (choď na krok 1)

Ukážme si konkrétny príklad (šedé políčka predstavujú indexy poľa, biele sú prvky poľa):

x=18
n=10

pole=

0	1	2	3	4	5	6	7	8	9	10
1	2	6	18	20	23	29	32	34	39	43

Pre implementáciu algoritmu binárneho vyhľadávania si musíme vypočítať hodnoty ľavého a pravého indexu poľa, v ktorom hľadáme. Na začiatok je to jednoduché:

lavy=0
pravy=n-1

• Porovnajme hľadaný prvok x=18 so stredným prvkom:

stred=(lavy+pravy)/2
stred=5

pole=

0	1	2	3	4	5	6	7	8	9	10
1	2	6	18	20	23	29	32	34	39	43

• pole[5] != x (23 != 18 )
  • platí že x<23 (resp. x<pole[stred])
  • budeme vyhľadávať vľavo (žltá časť)
    • lavy zostane nezmeneny (0)
    • pravy=stred - 1 (4)

• Porovnajme hľadaný prvok x=18 so stredným prvkom:

stred=(lavy+pravy)/2 = (0+4)/2=2
stred=2

pole=

0	1	2	3	4	5	6	7	8	9	10
1	2	6	18	20	23	29	32	34	39	43

• pole[2] != x (6 != 18 )
  • platí že x>6 (resp. x>pole[stred])
  • budeme vyhľadávať vpravo (žltá časť)
    • lavy = stred + 1 (3)
    • pravy zostane nezmeneny (4)

• Porovnajme hľadaný prvok x=18 so stredným prvkom:

stred=(lavy+pravy)/2 = (3+4)/2=3
stred=3

• pole[3] == x (18 = 18 )
• Stredný prvok je zhodný s hľadaným
• Algoritmus končí
  • Výsledok je index nájdeného prvku, teda stred. V našom príklade je to 3.

Binárne vyhľadávanie - zdrojový kód v jazyku C

Názov funkcie	hladajBinarne hladajBinarneR
Návratová hodnota	index nájdeného prvku (-1 pri neúspechu)
Parametre	pole prvkov - pole rozmer poľa - n hľadaný prvok - x
Zložitosť algoritmu	O(Log(n))

Keďže samotné definícia binárneho vyhľadávania je rekurzívna, uvádzame aj rekurzívnu verziu funkcie.

Binárne vyhľadávanie - jazyk C

Iteračná verzia	Rekurzívna verzia
int hladajBinarne(int *pole,int dlzka, int x) { int najdene=0; int lavy = 0, pravy = dlzka - 1, stred; while ( (lavy <= pravy) && (najdene==0) ) { stred = (lavy + pravy) / 2; if (pole[stred] == x) najdene=1; else if (pole[stred] < x) lavy = stred + 1; else pravy=stred - 1; } if(najdene==1) return stred; else return -1; }	int hladajBinarneR(int *pole,int lavy, int pravy, int x) { if(lavy>pravy) return -1; else { int stred=(lavy+pravy)/2; if(pole[stred]==x) return stred; else { if( x<pole[stred] ) return hladajB(pole,lavy,stred-1,x); else return hladajB(pole,stred+1,pravy,x); } } }

http://en.wikipedia.org/wiki/Binary_search

Ternárne vyhľadávanie

Predpoklad správneho vyhľadávania je, že prvku sú v poli usporiadané. Postup vyhľadávania je podobný ako pri binárnom vyhľadávaním abšak pole nerozdelíme na polovicu ale na tretiny.

Použité premenné

• pole - jednorozmerné pole, v ktorom budeme vyhľadávať
• x - prvok, ktorý hľadáme
• n - veľkosť pola pole.
• i, j - rozsah poľa, (začiatok , koniec) kde budeme hľadať.
• m1 - index prvku v prvej tretine
• m2 - index prvku v druhej tretine

1. Rozdeľ pole na tretiny
   1. m1=( i*2 + j ) / 3;
   2. m2=( i + j*2 ) / 3;
2. Porovnaj, či sa hľadaný prvok zhoduje z prvkom na indexe m1, ak áno, tak koniec. Výsledok je index m1
3. Porovnaj, či sa hľadaný prvok zhoduje z prvkom na indexe m2, ak áno, tak koniec. Výsledok je index m2
4. Ak platí i>j, skonči, prvok x sa v poli nenachádza.
5. Ak je hľadaný prvok menší ako prvok pole[m1], tak hľadaj v prvej tretine poľa
   • i zostáva nezmenené , j=m1-1. Choď na krok 1.
6. Ak je hľadaný prvok väčší ako prvok pole[m2], tak hľadaj v tretej tretine poľa
   • i = m2+1 , j zostáva nezmenené. Choď na krok 1.
7. inak hľadaj v druhej tretine poľa
   • i = m1+1 , j=m2-+. Choď na krok 1.

Uveďme príklad: V prechádzajúcom príklade hľadajme číslo x=39

Na začiatku máme:

i=0
j=10

Vypočítame m1, m2

m1=( i*2 + j ) / 3 = (0+10)/3 = 3
m2=( i + j*2 ) / 3 = (0+20)/3 = 6

pole=

0	1	2	m1=3	4	5	m2=6	7	8	9	10
1	2	6	18	20	23	29	32	34	39	43

Teraz hľadáme v tretej tretine poľa:

i=m2+1=7
j=10

Vypočítame m1, m2

m1=( i*2 + j ) / 3 = (14+10)/3 =8
m2=( i + j*2 ) / 3 = (7+20)/3 = 9

pole=

0	1	2	3	4	5	6	7	m1=8	m2=9	10
1	2	6	18	20	23	29	32	34	39	43

Platí, že x=pole[m2]. Výsledkom bude teda hodnota m2 (index nájdeného prvku v poli)

Ternárne vyhľadávanie - zdrojový kód v C

Názov funkcie	hladajTernarne
Návratová hodnota	index nájdeného prvku (-1 pri neúspechu)
Parametre	pole prvkov - pole rozmer poľa - n hľadaný prvok - x
Zložitosť algoritmu	O()

int hladajTernarne(int pole[],int i,int j,int x) {
  int m1,m2;
  m1=( i*2 + j ) / 3;
  m2=( i + j*2 ) / 3;
  if(x==pole[m1])
    return m1;
  if(x==pole[m2])   
    return m2;
  if(i>j) return -1; // prvok sa nenašiel  
  if(x<pole[m1]) // hľadaj v prvej tretine
    return(hladajTernarne(pole, i,m1-1,x));
  if(x>pole[m2])  // hľadaj v druhej tretine
    return(hladajTernarne(pole, m2+1,j,x));
  else   // hľadaj v tretej tretine
    return(hladajTernarne(pole, m1+1,m2-1,x));
}

http://en.wikipedia.org/wiki/Ternary_search

Interpolačné vyhľadávanie

http://en.wikipedia.org/wiki/Interpolation_search