Binární vyhledávání

Najde hodnotu v seřazeném poli tak, že se podívá doprostřed a zahodí polovinu, ve které být nemůže. Každé porovnání zbytek zmenší na polovinu.

nejlepší Ω(1)
průměrný Θ(log n)
nejhorší O(log n)
paměť O(1)

Co to znamená?

Seřazené: vzestupně uspořádané. Binární vyhledávání to potřebuje; na neseřazených datech dává špatné odpovědi.
Půlení: každé porovnání zahodí polovinu zbytku, tu, ve které cíl být nemůže.
log₂ n: kolikrát lze n rozpůlit, než zbude 1. Pro 64 hodnot je to 6, tedy nejvýš 7 porovnání.

střed (mid)
nalezeno
vyloučeno
cíl

0 / 14 kroků

Každý střed, který by hledání mohlo zvolit; běh je jedna cesta dolů. Úrovně: 5 = ⌈log₂(24 + 1)⌉, nejvíc porovnání, kolik může potřebovat.

Rychlost 8 kroků/s

Mezerník: přehrát nebo pozastavit. Šipky vlevo/vpravo: krok. Home a End: přeskočit.

Zkuste: Vyberte cíl, který v poli není. Hledání i tak skončí nejvýš po ⌈log₂(n + 1)⌉ porovnáních, když lo předběhne hi.

Jak to funguje

Binární vyhledávání drží dvě značky, lo a hi, kolem části pole, kde může cíl ještě být. Podívá se na hodnotu uprostřed: je-li to cíl, konec; je-li menší, cíl může být jen vpravo, takže lo se posune za střed; je-li větší, hi se posune před něj. Každý krok zbytek půlí: 64 hodnot potřebuje nejvýš 7 porovnání a milion nejvýš 20. Když lo předběhne hi, nic nezbývá: hodnota v poli není.

Kdy se hodí

Binární vyhledávání použijte vždy, když jsou data seřazená a lze skočit na libovolnou pozici: slovo v seřazeném seznamu, verze v historii vydání, git bisect, místo pro vložení do seřazeného pole. Na neseřazených datech dává špatné odpovědi a řadit předem se vyplatí až při mnoha hledáních.