Binární vyhledávání

Algoritmy Vyhledávání Binární vyhledávání

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 pravou 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 pravou 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 pravou 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 pravou polovinu
      end
    end
  end
  return -1
end

 

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

 

  Aktivity (1)

Článek pro vás napsal David Čápka
Avatar
Autor pracuje jako softwarový architekt a pedagog na projektu ITnetwork.cz (a jeho zahraničních verzích). Velmi si váží svobody podnikání v naší zemi a věří, že když se člověk neštítí práce, tak dokáže úplně cokoli.
Unicorn College Autor se informační technologie naučil na Unicorn College - prestižní soukromé vysoké škole IT a ekonomie.

Jak se ti líbí článek?
Celkem (4 hlasů) :
55555


 


Miniatura
Předchozí článek
Sekvenční vyhledávání
Miniatura
Všechny články v sekci
Vyhledávací algoritmy
Miniatura
Následující článek
Interpolační vyhledávání

 

 

Komentáře

Avatar
trantanh
Člen
Avatar
trantanh:

ahoj,chci se zeptat, co kdyz mam pole 6 prvku (sudy), jak z toho mam vzit prostredni prvek, abych mohl porovnavat?
Diky za odpoved.

 
Odpovědět 13.6.2015 16:58
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na trantanh
Jan Vargovský:

Prostě to vyděl dvěma na celé čísla.

 
Odpovědět 13.6.2015 17:08
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 2 zpráv z 2.