Binárne vyhľadávanie

Z Wikipédie

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, 1 + log₂N 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.

[úprava] Implementácie

Rekurzívna implementácia binárneho vyhľadávania v jazyku Python:

def binarySearch(zoznam, hodnota, vlavo, vpravo):
    if vpravo < vlavo:
        return False
    stred = (vpravo + vlavo) / 2
    if zoznam[stred] == hodnota:
        return True
    if hodnota < zoznam[stred]:
        binarySearch(zoznam, hodnota, vlavo, stred - 1)
    else:
        binarySearch(zoznam, hodnota, stred + 1, vpravo)

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 = (vpravo + vlavo) / 2
        if zoznam[stred] == hodnota:
            return True
        if hodnota < zoznam[stred]:
            vpravo = stred - 1
        else:
            vlavo = stred + 1
    return False