Binárne vyhľadávanie

Binárne vyhľadávanie je vyhľadávací algormitmus na nájdenie zadanej hodnoty v usporiadanom zozname pomocou skracovania zoznamu o polovicu v každom kroku. 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.

Binárne vyhľadávanie je algoritmus s logaritmickou zložitosťou O(log n). Presnejšie,  iterácií je potrebných na získanie výsledku. Je 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 vo veľa programovacích jazykoch je rekurzívny zápis oveľa elegantnejší.

Binárne vyhľadávanie je príkladom algoritmu typu rozdeľ a panuj.

 Implementácie 
Rekurzívna implementácia binárneho vyhľadávania v jazyku Python 3:
def binarySearch(zoznam, hodnota, vlavo, vpravo):
    if vlavo > vpravo:
        return -1     # hodnota nenajdena
    stred = vlavo + int((vpravo - vlavo) / 2)

    if   hodnota < zoznam[stred]:
        return binarySearch(zoznam, hodnota, vlavo, stred - 1)
    elif hodnota > zoznam[stred]:
        return binarySearch(zoznam, hodnota, stred + 1, vpravo)
    else:
        # zoznam[stred] == hodnota:
        return stred

Vďaka tomu, že rekurzívne volania sú na konci funkcie (koncová rekurzia), je možné túto implementáciu prepísať len pomocou cyklu
def binarySearch(zoznam, hodnota, vlavo, vpravo):
    while vlavo <= vpravo:
        stred = vlavo + int((vpravo - vlavo) / 2)

        if   hodnota < zoznam[stred]:
            vpravo = stred - 1
        elif hodnota > zoznam[stred]:
            vlavo  = stred + 1
        else:
            # zoznam[stred] == hodnota
            return stred

    return -1      # hodnota nenajdena

 Implementačné komplikácie 
Keď Jon Bentley priradil binárne vyhľadávanie ako problém pre kurz profesionálnych programátorov, zistil, že 90% z nich nedokáže poskytnúť správne riešenie. Ďalšia štúdia publikovaná v roku 1988 ukazuje, že správny kód pre binárne vyhľadávanie sa dá nájsť len v 5 z 20 učebniciach.

Bentley-ho vlastná implementácia binárneho vyhľadávania, publikovaná v roku 1986 v knihe Programming Pearls, obsahovala chybu ktorá pri vysokých číslach zbytočne spôsobovala prekročenie maximálnej veľkosti premennej typu integer. Chyba nebola odhalená viac ako 20 rokov.https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html V oficiálnej knižnici jazyka Java sa vyskytovala rovnaká chyba po dobu viac než 9 rokov.http://bugs.java.com/bugdatabase/view_bug.do?bug_id=5045582
Ukážkový kód algoritmu, ktorý bol na tejto stránke, pred úpravou túto chybu obsahoval tiež.

 Referencie 

Kategória:Vyhľadávacie algoritmy