Algoritmy pre usporiadané zoznamy

Vyhľadávanie v obojsmerne zreťazenom zozname podľa aktuálnej pozície

Popis
Ak chceme vyhľadávať v zoradenom poli, môžeme výhodu zoradenia využiť na zvýšenie efektivity. Ako bolo opísané pri predchádzajúcom algoritme, môžeme zoznam prehľadávať od začiatku po koniec, ale pri obojsmerne zreťazenom zozname tak robiť nemusíme. Ak sa pohybujeme v takomto zozname, zväčša poznáme aktuálnu pozíciu niekde uprostred v tomto zozname. Ak chceme vyhľadávať, môžeme smer vyhľadávania prispôsobiť tejto aktuálnej pozícii.

Vstupy algoritmu
Vstupom je obojsmerne zreťazený zoznam, hľadaný prvok v zozname a ako bolo spomenuté aj aktuálna pozícia v zozname, od ktorej chceme začať vyhľadávanie.

Princíp činnosti
Najprv sa porovná hľadaný prvok s prvkom, ktorý sa nachádza v aktuálnom zázname. Ak je hľadaný prvok menší, je zrejmé že vyhľadávanie by malo pokračovať v predchádzajúcich záznamoch zoznamu. Ak je hľadaný prvok väčší, pokračuje algoritmus vo vyhľadávaní v nasledujúcich záznamoch. Vyhľadávanie pokračuje posúvaním sa po záznamoch v smere, ktorý bol určený na začiatku vyhľadávania dovtedy, pokiaľ nie je nájdený hľadaný prvok alebo pri postupe k menším (resp. väčším) prvkom nie je nájdený prvok menší (resp. väčší) ako hľadaný. To by znamenalo, že ak hľadaný prvok v poli mal byť, musel už byť prejdený. Pretože pri postupe k menším (resp. väčším) prvkom na predpokladanej pozícii hľadaný prvok nebol, ale bol tam už prvok menší (resp. väčší) ako hľadaný, hľadaný prvok sa v zozname nenachádza.

Výstupy algoritmu
Tak ako pri predchádzajúcom algoritme, výstupom môže byť logická premenná s hodnotou pravda/nepravda, podľa toho, či sa hľadaný prvok v poli nachádzal. Druhou používanou možnosťou výstupu je ukazovateľ na nájdený záznam, ktorý obsahuje hľadaný prvok. V prípade, že v zozname hľadaný prvok nie je, je výstupom nulový ukazovateľ.

Vývojový diagram

Implementácia

 
//sekvencne vyhladavanie zadanej hodnoty "hladany" v OZ zozname od zaznamu "aktualny" s podmienkou
//zoznam musi byt vzostupne usporiadany 
//(na zaciatku zoznamu je zaznam s najmensou hodnotou)
//zoznam musi byt ukonceny nulovymi ukazovatelmi
//funkcia vracia ukazovatel na najdeny zaznam (v pripade neuspechu vyhladavania vracia 0	
CZaznam_OZ* OZnajdi_sekv1_zaznam_podm(int hladany, CZaznam_OZ* aktualny){
	if (!aktualny) return 0;
	if (aktualny->hodnota()==hladany) return aktualny;

	if (hladany < aktualny->hodnota()) {
		do {
			aktualny=aktualny->predch();
			if (!aktualny) return 0;
		} while (hladany < aktualny->hodnota());
	if (aktualny->hodnota()==hladany) return aktualny;
	else return 0;
	}
	else {
		do {
			aktualny=aktualny->dalsi();
			if (!aktualny) return 0;
		} while (hladany > aktualny->hodnota());
	if (aktualny->hodnota()==hladany) return aktualny;
	else return 0;
	}
}

Vizualizácie

Časová zložitosť
Časová zložitosť závisí najmä od aktuálnej pozície pred samotným vyhľadávaním. V najhoršom prípade je však približne 2*n, pretože pri prehľadávaní môže algoritmus prejsť najviac n záznamov a v každom cykle robí 2 porovnania.

Porovnanie s predchádzajúcimi algoritmami
Tento algoritmus robí síce v najhoršom prípade rovnaký počet porovnaní ako obyčajné sekvenčné prehľadávanie, ale v priemernom prípade by mal mať počet porovnaní menší.