Binární vyhledávání najde cíl v seřazeném poli tím, že opakovaně dělí rozsah vyhledávání na poloviny. Každé porovnání eliminuje polovinu zbývajících prvků, čímž dosahuje O(log n) času.
Podívejte se na střední prvek. Pokud se rovná cíli, hotovo. Pokud je cíl menší, prohledejte levou polovinu; pokud je větší, prohledejte pravou polovinu. Opakujte, dokud není prvek nalezen nebo dokud není rozsah prázdný.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2 # middle index
if arr[mid] == target:
return mid # found it
elif arr[mid] < target:
lo = mid + 1 # discard left half
else:
hi = mid - 1 # discard right half
return -1 # not present
binary_search([1, 3, 5, 7, 9], 7) # -> 3
Search 7 in [1,3,5,7,9]
lo=0 hi=4 mid=2 -> 5 < 7 => lo=3
lo=3 hi=4 mid=3 -> 7 == 7 => return 3
Vstup musí být seřazen — jinak jsou výsledky nesmysluplné. Dávejte pozor na chyby typu off-by-one v lo/hi a přetečení celých čísel v některých jazycích (použijte lo + (hi-lo)//2).
Dělení prostoru vyhledávání na poloviny změní vyhledávání v poli s milionem prvků na ~20 porovnání.
Vzor dělení a vítězství (divide-and-conquer), který je za tím skrytý, se znovu objevuje ve stromech, databázích a nespočetných interview problémech.
Znalost jeho jedné zásadní podmínky — seřazeného vstupu — vás zachrání před klasickou jemnou chybou.