Dvojiško iskanje

Iz Wikipedije, proste enciklopedije
(Preusmerjeno s strani Binarno iskanje)
Skoči na: navigacija, iskanje

Dvojiško iskanje (ali binarno iskanje) je optimalni algoritem za iskanje v urejeni tabeli, ki temelji na strategiji deli in vladaj.

Hitrejše iskanje je v splošnem mogoče, če se porazdelitev elementov v tabeli vnaprej pozna ali pa se jo med iskanjem oceni. Ta algoritem se imenuje interpolacijsko iskanje.

Delovanje[uredi | uredi kodo]

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 se naleti 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[uredi | uredi kodo]

Iskanje poteka tako, da se pri vsakem koraku izloči polovica podatkov, zato je časovna zahtevnost dvojiškega iskanja O(\operatorname{lb} n)\, , kjer je \operatorname{lb}\, dvojiški logaritem.

Psevdokoda[uredi | uredi kodo]

  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

Zunanje povezave[uredi | uredi kodo]