Dvojiško iskanje

Iz Wikipedije, proste enciklopedije
(Preusmerjeno s strani Binarno iskanje)
Skoči na: navigacija, iskanje
Dvojiško iskanje
Binary search into array - example.svg
Primer delovanja algoritma za dvojiško iskanje (v tem primeru je iskana vrednost 4).
Osnovni podatki
Vrsta: algoritem za iskanje
Podatkovna struktura: tabela
Časovna zahtevnost
Zgornja meja zahtevnosti: O(log n)
Spodnja meja zahtevnosti: O(1)
Pričakovana zahtevnost: O(log n)
Prostorska zahtevnost
Prostorska zahtevnost: O(1)


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.

Opis[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]

V najboljšem primeru (če je iskani element na srednjem indeksu tabele) je časovna kompleksnost algoritma O(1)\, . Iskanje poteka tako, da se pri vsakem koraku izloči polovica podatkov, zato je časovna zahtevnost dvojiškega iskanja O(\operatorname{log} n)\, , kjer je \operatorname{log}\, dvojiški logaritem.

Zapis[uredi | uredi kodo]

Rekurzivno[uredi | uredi kodo]

Algoritem je mogoče zapisati na več načinov, najbolj enostavno z uporabo rekurzije. Ko prvič pokličemo funkcijo ji podamo tabelo z vrednostmi, ki so razvrščene v naraščajočem vrstnem redu, iskano vrednost ter prvi in zadnji indeks v tabeli. Algoritem nato poišče srednjo vrednost, se odloči v kateri podmnožici je rešitev in opravi rekurzivni klic s to podmnožico (tabelo).

int dvojiskoIskanje(int tabela[], int kljuc, int levi, int desni)
{
  if (levi < desni)
    // Tabela je prazna, kljuc ni bil najden
    return -1;

  else
    {
      // Izračunaj indeks srednjega elementa
      int srednji = (levi + desni) / 2;
     
      if (kljuc < tabela[srednji])
        // Ključ je v spodnji podmnožici
        return dvojiskoIskanje(tabela, kljuc, levi, srednji - 1);

      else if (kljuc > tabela[srednji])
        // Ključ je v zgornji podmnožici
        return dvojiskoIskanje(tabela, kljuc, srednji + 1, desni);

      else
        // Ključ je najden
        return srednji;
    }
}

Iterativno[uredi | uredi kodo]

Ravno tako je algoritem za dvojiško iskanje mogoče napisati iterativno, z uporabo dveh spremenljivk glede na kateri se krči podmnožica za iskanje.

int dvojiskoIskanje(int tabela[], int kljuc, int levi, int desni)
{
  while (levi <= desni) 
  {
      //Izračunaj indeks srednjega elementa
      sredina = (levi + desni) / 2;

      if (kljuc > tabela[sredina])
          // Ključ je v zgornji podmnožici
          levi = sredina + 1;

      else if (kljuc < tabela[sredina])
          // Ključ je v spodnji podmnožici
          desni = sredina - 1;

      else
          // Ključ je najden
          return sredina;
  }
  //Ključa ni v tabeli
  return -1;
}

Glej tudi[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]