Dvojiško iskanje: Razlika med redakcijama
m r2.6.4) (robot Dodajanje: el:Δυαδική αναζήτηση |
m →Psevdokoda: povezava na wikibooks |
||
Vrstica 22: | Vrstica 22: | ||
return -1; // ključa ni v tabeli |
return -1; // ključa ni v tabeli |
||
</source> |
</source> |
||
== Zunanje povezave == |
|||
{{Wikibooks|Algorithm implementation|Search/Binary search|Binary search}} |
|||
{{comp-stub}} |
{{comp-stub}} |
Redakcija: 13:11, 19. januar 2012
Binarno iskanje je optimalen algoritem za iskanje v urejeni tabeli, ki temelji na strategiji deli in vladaj.
Hitrejše iskanje je v splošnem mogoče, če porazdelitev elementov v tabeli vnaprej poznamo ali pa jo med iskanjem ocenimo. Ta algoritem se imenuje interpolacijsko iskanje.
Delovanje
Algoritem na začetku za interval preiskovanja vzame celotno tabelo, nato pa v vsakem naslednjem koraku vzame element na sredini intervala in ga primerja z iskanim ključem. Če je element večji od ključa, potem element postane nova zgornja meja intervala, sicer postane nova spodnja meja. Iskanje se zaključi, ko naletimo na iskani element, ki je enak ključu, če takega elementa ni, pa se iskanje zaključi, ko se zgornja in spodnja meja intervala preiskovanja prekrijeta.
Zahtevnost
Iskanje poteka tako, da se pri vsakem koraku izloči polovica podatkov, zato je časovna zahtevnost binarnega iskanja .
Psevdokoda
while (levi <= desni) {
sredina = (levi+desni)/2;
if (kljuc > tabela[sredina])
levi = sredina + 1;
else if (kljuc < tabela[sredina])
desni = sredina - 1;
else
return sredina;
}
return -1; // ključa ni v tabeli