Lekce 3 - Binární vyhledávání
V minulé lekci, Sekvenční vyhledávání, jsme si ukázali velmi jednoduchý algoritmus pro vyhledávání prvku v nesetříděné datové struktuře (poli, seznamu) a jeho následné vylepšení malým trikem.
Základním problémem vyhledávání je struktura, ve které máme data uložená. Pokud budeme mít uloženo milion zaměstnanců v obyčejném poli a budeme mezi nimi chtít najít zaměstnance s platem 36.597 kč, nezbude nám nic jiného, než celé pole projet cyklem od začátku do konce, kdy můžeme jen doufat, že cestou někdy narazíme na hledaný prvek. Nejlepší případ jistě bude, když hledaný zaměstnanec bude hned na prvním indexu v poli, nejhorší bude ten, kdy tam zaměstnanec vůbec nebude a my musíme projet celé milion prvků dlouhé pole, abychom na to přišli. Průměrná časová složitost takového naivního algoritmu by byla O(n), kde n je délka pole.
Vyhledávání lze však výrazně urychlit tím, když si budeme udržovat pole setříděné. Algoritmus, který se používá pro vyhledávání prvků v setříděném poli, se nazývá binární vyhledávání. Binární proto, že dělí pole na dvě poloviny. Má následující průběh:
- Podíváme se na hodnotu uprostřed pole (prostřední index není problém získat, když známe délku pole, jen ji vydělíme dvěma)
- Pokud je hledaný prvek menší, než ten, který se nachází v prostředku pole, omezíme se pouze na levou polovinu pole a pravé si nebudeme všímat. Pokud je větší, omezíme se na pravou polovinu pole a nebudeme si všímat té levé. Můžeme to udělat díky tomu, že si jsme jisti, že v této polovině se prvek nemůže nacházet, protože je na to moc velký.
- Na zbylou polovinu aplikujeme to samé pravidlo, opět se podíváme doprostřed a zaměříme se jen na jednu polovinu této poloviny pole (už nás tedy zajímá jen 1/4 původního pole). Postup opakujeme, čímž se stále přesněji a přesněji přibližujeme k hledanému prvku. Obvykle stačí jen pár kroků k nalezení prvku, který hledáme.
- Končíme v tu chvíli, kdy je v prostředku prvek, který hledáme nebo jakmile už nemáme co dělit - tehdy tam hledaný prvek není.
Když se nad algoritmem zamyslíme, zjistíme, že v každém kroku zahodíme celou polovinu pole, která nás vlastně nezajímá, protože víme, že se v ní hledaný prvek nemůže nalézat. Složitost bude tedy O(log n), kde základem logaritmu bude 2 (protože dělíme na 2 poloviny). Toto zrychlení je obrovské a jedná se o nejlepší možnou složitost problému vyhledávání. Existují sice algoritmy, které mohou hledat rychleji, ale bohužel je to vykoupeno špatnými nejhoršími případy.
Protože nic není dokonalé, naskýtá se i zde problém. Tímto problémem
je vlastnost struktury pole, která sice umožňuje rychle přistupovat k
prvkům pomocí indexu, ale pokud chceme do pole prvky přidávat nebo mazat,
musíme pole zvětšit a prvky po jednom poposouvat, abychom vytvořili místo
na nový prvek, který chceme vložit někam dovnitř. Tato operace je
neskutečně časově nákladná. Nesmíme zapomenout na to, že pole si musíme
udržovat setříděné. Pokud nějaký prvek přidáme, musíme ho vložit na
místo, kam patří. Představte si pole velké milion, kde nově vkládaný
prvek patří někam doprostřed - musíme provést půl milionu posunů doprava
a vytvořit uprostřed volné místo. Někdo by mohl namítat, že bychom mohli
použít spojový seznam, tam se sice vkládá v konstantním čase, ale zase
nemůžeme rychle přistupovat k indexům. Řešení bude tedy někde
uprostřed, existují totiž speciální struktury zvané vyhledávací stromy,
které oba problémy řeší. Ale o tom až příště 
Pokud chcete v poli jen vyhledávat, nic lepšího než binární vyhledávání není (pokud neznáte o datech nějakou další vlastnost). Pokud chcete hodně vyhledávat a občas něco přidat nebo umazat, pořád se algoritmus vyplatí. Pokud však potřebujete vyhledávat a i pole měnit, je to problém a čtěte další algoritmy v této sekci.
Algoritmus binárního vyhledávání je možné zapsat s rekurzí i bez rekurze. Tradičně začneme řešením bez rekurze.
Zdrojový kód - bez rekurze
-
public static int binary_search(int[] array, int item) { int left = 0; int right = array.length - 1; int center; if ((item < array[left]) || (item > array[right])) // prvek mimo rozsah return -1; while (left <= right) { // pokud mame co delit center = (left + right) / 2; if (item == array[center]) return center; // nalezeno else if (item < array[center]) right = center - 1; // vyhodime pravou polovinu else left = center + 1; // vyhodime levou polovinu } return -1; }
-
public static int binary_search(int[] array, int item) { int left = 0; int right = array.Length - 1; int center; if ((item < array[left]) || (item > array[right])) // prvek mimo rozsah return -1; while (left <= right) { // pokud mame co delit center = (left + right) / 2; if (item == array[center]) return center; // nalezeno else if (item < array[center]) right = center - 1; // vyhodime pravou polovinu else left = center + 1; // vyhodime levou polovinu } return -1; }
-
function binary_search(anarray: array of integer; item: integer): integer; var left, right, center: integer; begin left:=0; right:=length(anarray) - 1; if ((item < anarray[left]) or (item > anarray[right])) then // prvek mimo rozsah begin result:=-1; exit; end; while (left <= right) do begin // pokud mame co delit center:=(left + right) div 2; if (item = anarray[center]) then begin result:=center; // nalezeno exit; end else if (item < anarray[center]) then right:=center - 1 // vyhodime pravou polovinu else left:=center + 1; // vyhodime levou polovinu end; result:=-1; end;
-
def binary_search(array, item) left = 0 right = array.length - 1 if ((item < array[left]) || (item > array[right])) # prvek mimo rozsah return -1 end while (left <= right) do # pokud mame co delit center = (left + right) / 2 if (item == array[center]) return center # nalezeno else if (item < array[center]) right = center - 1 # vyhodime pravou polovinu else left = center + 1 # vyhodime levou polovinu end end end return -1 end
-
{PHP} function binary_search($array, $item) { $left = 0; $right = count($array) - 1; if (($item < $array[$left]) || ($item > $array[$right])) // prvek mimo rozsah return -1; while ($left <= $right) { // pokud mame co delit $center = (int)(($left + $right) / 2); // přetypujeme na int, ať nemáme des. číslo if ($item == $array[$center]) return $center; // nalezeno else if ($item < $array[$center]) $right = $center - 1; // vyhodime pravou polovinu else $left = $center + 1; // vyhodime levou polovinu } return -1; } $list = [1, 4, 7, 8, 10, 16, 17, 18, 19, 20]; $item = 16; echo "Prvek ".$item." je na pozici ". binary_search($list, $item); {/PHP}
Rekurzivní řešení je zde o něco elegantnější, ale zase je vykoupeno větší paměťovou náročností.
Zdrojový kód - s rekurzí
-
public static int binary_search(int[] array, int item, int left, int right) { int center; if (left > right) return -1; center = (left + right) / 2; if (item < array[center]) return binary_search(array, item, left, center - 1); // vyhodime pravou polovinu if (item > array[center]) return binary_search(array, item, center + 1, right); // vyhodime levou polovinu return center; // nalezeno }
-
public static int binary_search(int[] array, int item, int left, int right) { int center; if (left > right) return -1; center = (left + right) / 2; if (item < array[center]) return binary_search(array, item, left, center - 1); // vyhodime pravou polovinu if (item > array[center]) return binary_search(array, item, center + 1, right); // vyhodime levou polovinu return center; // nalezeno }
-
function binary_search(anarray: array of integer; item, left, right: integer): integer; var center: integer; begin if (left > right) then begin // nemame co delit result:=-1; exit; end; center:=(left + right) div 2; if (item < anarray[center]) then result:=binary_search(anarray, item, left, center - 1); // vyhodime pravou polovinu if (item > anarray[center]) then result:=binary_search(anarray, item, center + 1, right); // vyhodime levou polovinu if (item = anarray[center]) then result:=center; // nalezeno end;
-
def binary_search(array, item, left, right) return -1 if (left > right) center = (left + right) / 2 if (item < array[center]) return binary_search(array, item, left, center - 1) # vyhodime pravou polovinu end if (item > array[center]) return binary_search(array, item, center + 1, right) # vyhodime levou polovinu end return center; # nalezeno end
-
{PHP} function binary_search($array, $item, $left, $right) { if ($left > $right) return -1; $center = (int)(($left + $right) / 2); if ($item < $array[$center]) return binary_search($array, $item, $left, $center - 1); // vyhodime pravou polovinu if ($item > $array[$center]) return binary_search($array, $item, $center + 1, $right); // vyhodime levou polovinu return $center; // nalezeno } $list = [1, 4, 7, 8, 10, 16, 17, 18, 19, 20]; $item = 18; echo "Prvek ".$item." je na pozici ". binary_search($list, $item, 0, count($list)-1); {/PHP}
V další lekci, Interpolační vyhledávání, si ukážeme algoritmus na interpolační vyhledávání, který efektivně vyhledává prvky v rovnoměrně setříděném poli.
David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.