Algoritmy pre usporiadané polia

Binárne vyhľadávanie

Popis
Algoritmus binárneho vyhľadávania neprehľadáva pole sekvenčne, ale pozíciu aktuálneho prvku, ktorý bude porovnávaný s hľadaným prvkom vypočítava. Pole delí vždy na polovicu až pokiaľ nenájde hľadaný prvok alebo nezistí, že hľadaný prvok sa v poli nenachádza. Podľa toho, či je aktuálny prvok väčší alebo menší ako hľadaný, vyhľadáva ďalej iba v ľavej alebo pravej časti poľa od aktuálneho prvku.

Vypočítanie pozície aktuálneho prvku 
poz_akt_prvku = (lava_hranica + prava_hranica) / 2

Vstupy algoritmu
Tento algoritmus potrebuje okrem vstupného zoradeného poľa prvkov a hľadaného prvku poznať aj počet prvkov v poli. Ten potom využije na nájdenie stredu, teda na určenie aktuálneho prvku poľa. Pole ukončené ukončovacím znakom nie je priamo použiteľné, pretože toto pole by musel najprv algoritmus prehľadať a určiť počet jeho prvkov, aby vedel určiť stred poľa. Preto je vhodnejšie aby vstupom algoritmu bol priamo počet prvkov.

Princíp činnosti
Podľa počtu prvkov poľa urči algoritmus aritmetický stred poľa. Prvok na tejto pozícii bude následne porovnaný s hľadaným prvkom a podľa výsledku sa určí ďalší postup. Ak bol hľadaný prvok náhodou presne v strede poľa, algoritmus sa úspešne ukončí a ďalšie prehľadávanie nie je nutné. Ak sa v strede poľa nachádzal prvok väčší ako hľadaný, je zrejmé, že ak sa hľadaný prvok v poli nachádza, potom bude niekde v ľavej polovici poľa, teda medzi prvkami menšími ako je aktuálny prvok. Ak je v strede poľa prvok menší ako hľadaný, bude hľadaný prvok hľadať medzi prvkami väčšími ako stredným a tie sa nachádzajú v pravej polovici poľa. Keďže takto pri každom porovnaní vie s istotou určiť, že v niektorej z polovíc sa hľadaný prvok určite nenachádza, pokračuje vo vyhľadávaní iba v tej druhej polovici, ktorá bude pre algoritmus od toho momentu novým vyhľadávacím poľom. Hranice tohto poľa sú pôvodná ľavá hranica poľa a stred – 1 prvok alebo stred + 1 prvok a pôvodná pravá hranica poľa podľa toho, v ktorej polovici poľa má vyhľadávanie pokračovať. Opakovaním tohto postupu buď nájdeme hľadaný prvok alebo sa postupne pravá a ľavá hranica budú približovať až dovtedy, pokiaľ sa nestotožnia a nebudú na rovnakom mieste v poli.

Výstupy algoritmu
Ak sa algoritmu podarí pri delení poľa na polovicu nájsť hľadaný prvok, potom sa skončí úspechom a hľadaný prvok našiel. Ak ale postupne pole delí až dovtedy, pokiaľ nebude ľavá hranica napravo od pravej hranice, je zrejmé, že sa prvok v poli nenachádzal. Ak by tam totiž bol, museli by sme ho už nájsť a musel by sa nachádzať medzi hranicami poľa. Výstupom algoritmu je index hľadaného prvku alebo –1, ak sa hľadaný prvok v poli nenachádzal.

Vývojový diagram

Implementácia

 
//binarne vyhladavanie zadaneho prvku "hladany" pomocou cyklu while
//pole "pole" s poctom prvkov "velkost" musi byt usporiadane vzostupne 
//(na zaciatku pola je prvok s najmensou hodnotou)
//funkcia vracia index zadaneho prvku v poli (v pripade neuspechu vyhladavania vracia -1)
int najdi_bin_cykl_index(int* pole, int velkost, int hladany){
	int lavy_o=0;
	int pravy_o=velkost-1;
	
	while(lavy_o <= pravy_o){
		int stred=(lavy_o + pravy_o)/2;
		if (pole[stred] < hladany) lavy_o=stred+1;
		else if (pole[stred] > hladany) pravy_o=stred-1;
		else return stred;
	}
	return -1;
}

Vizualizácie

Časová zložitosť
Keďže algoritmus pri každom cykle delí pole na polovicu, delí sa vyhľadávací problém vždy na problém polovičný. Počet cyklov je teda v najhoršom prípade podľa [4] rádovo log(2) n. V priemernom prípade úspešného hľadania je hľadaný prvok podľa [4] nájdený v predposlednom kroku, čo znamená, že priemerná časová zložitosť algoritmu je rádovo (log(2) n) – 1 porovnaní.

Porovnanie s predchádzajúcimi algoritmami
Tento algoritmus je veľmi efektívnym a zároveň univerzálnym algoritmom používaným v usporiadanom poli. Drobnou nevýhodou je síce delenie číslom 2 v každom kroku, ale toto delenie sa môže realizovať nenáročným bitovým posunom delenca vpravo. Pre polia s veľkým počtom prvkov je jeho efektivita omnoho vyššia ako efektivita ktoréhokoľvek sekvenčného algoritmu.