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

Binárne vyhľadávanie

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

Ternárne vyhľadávanie

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

Interpolačné vyhľadávanie

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

<pLines ymin=0 axiscolor=888888 cubic angle=90 plots legend xtitle=pocet_cisel ytitle=cas_[s]> ,binarne,ternarne 1 000, 2.115, 2.094 5 000, 2.537, 2.513 10 000, 2.674, 2.622 50 000, 3.028, 3.005 100 000, 3.252, 3.032 500 000, 3.642, 3.358 1 000 000, 3.719, 3.471 5 000 000, 4.129, 3.771 10 000 000, 4.410, 3.963 50 000 000, 5.679, 4.304 100 000 000, 5.806, 5.248 </pLines>