Zaradenie a popis

Binárne vyhľadávanie, alebo bisekcia, je vyhľadávacia technika na nájdenie danej hodnoty v utriednom poli prvkov.
V každom kroku sa rozpolí interval na dva podintervaly a prvok sa hľadá už len v jednom z nich.

^ TOP

Motivácia a špecifikácia

Máme utriedené pole A a máme nájsť kde sa v ňom nachádza prvok s hodnotou v.
Vstup: postupnosť n čísel A=<a1, a2,..., a n> a hodnota v.
Výstup: Index i taký, že v=A[i] alebo v=NIL, ak sa v nenachádza v A.

^ TOP

Myšlienka algoritmu

Binárne vyhľadávanie nájde medián, urobí porovnanie a na základe tohoto sa rozhodne o pokračovaní v hornej alebo dolnej časti zoznamu a rekurzívne sa pokračuje od začiatku. Toto sa vykonáva, až kým sa nenájde hľadaný prvok.

^ TOP

Vizualizácia

Postupne sa vyberá medián, pole sa rozdeľuje.
Ružovou farbou je označená časť poľa, kde sa prvok určite nenachádza.

^ TOP

Zápis algoritmu

     int search( key, r )
     typekey key;  dataarray r;

     { int high, i, low;
     for ( low=(-1), high=n;  high-low > 1;  )
          {
          i = (high+low) / 2;
          if ( key <= r[i].k )  high = i;
               else             low  = i;
          }
     if ( key==r[high].k )  return( high );
          else              return( -1 );
     }
      

^ TOP

Vlastnosti algoritmu

Binárne vyhľadávanie je algoritmus s logaritmickou časovou zložitosťou O(logn). Presnejšie, 1 + log2n iterácií je potrebných na získanie výsledku. Je teda značne rýchlejšie ako lineárne vyhľadávanie, ktoré má zložitosť O(n).
Dá sa vyjadriť rekurzívne aj iteratívne, avšak v mnohých programovacích jazykoch je rekurzívny zápis oveľa čitateľnejší.
Binárne vyhľadávanie je príkladom algoritmu typu rozdeľuj a panuj.

^ TOP

Implementácia a experimentovanie

Computer Science and Software Engineering, University of Canterbury, New Zealand
Java applet na pokusy s binárnym vyhľadávaním.
http://www.cosc.canterbury.ac.nz/mukundan/dsal/BSearch.html

Department of Mathematics, Arizona State University, USA
Applet na pokusy so binárnym vyhľadávaním.
http://desdemona.la.asu.edu/~mat243/applets/BS/BSApplet.php

^ TOP