Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

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
  • 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;
    }
    
    

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
  • 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
    }
    
    

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.


 

Předchozí článek
Sekvenční vyhledávání
Všechny články v sekci
Vyhledávací algoritmy
Přeskočit článek
(nedoporučujeme)
Interpolační vyhledávání
Článek pro vás napsal David Hartinger
Avatar
Uživatelské hodnocení:
32 hlasů
David je zakladatelem ITnetwork a programování se profesionálně věnuje 15 let. Má rád Nirvanu, nemovitosti a svobodu podnikání.
Unicorn university David se informační technologie naučil na Unicorn University - prestižní soukromé vysoké škole IT a ekonomie.
Aktivity