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 4 - Interpolační vyhledávání

V minulé lekci, Binární vyhledávání, jsme si ukázali efektivní binární vyhledávání, které vyhledává prvky v setříděném poli.

Interpolační vyhledávání je algoritmus velmi podobný binárnímu vyhledávání a používá se při vyhledávání na setříděném poli v případě, že víme, že jsou data rovnoměrně rozložená. Následující text bude tedy navazovat na lekci binární vyhledávání. V kódu se tyto dva algoritmy liší v podstatě jen na jednom řádku, a to je výběr kandidáta, tedy prvku, o kterém si myslíme, že by mohl být tím, co hledáme. V binárním vyhledávání byl tento prvek vždy střed pole.

Pokud si ale jsme jisti, že data v našem poli jsou rovnoměrně rozložená, je naprosto zbytečné dívat se do středu, když můžeme být mnohem přesnější. Pokud bychom opět hledali mezi zaměstnanci, ale tentokrát podle jména a hledali bychom pana Emila Zlého, je nám jasné, že nemá smysl dívat se doprostřed, protože lidé od Z budou jistě někde ke konci. Pokud bychom hledali paní Dolejší, bude někde kousek od začátku.

Jak zjistíme, ve kterém místě máme prvek hledat? Využijeme totiž poměrů a aby byla celá situace ještě přehlednější, zakreslil jsem ji přes podobnost trojúhelníků.

Interpolační vyhledávání - Vyhledávací algoritmy

Jak je vidět, na svislou osu jsou nanesené hodnoty v poli. LL je hodnota na nejlevějším indexu v poli, může to být třeba paní Bartošková. RR je hodnota na nejpravějším indexu, tou může být třeba pan Vendelín. Hodnota XX je paní Dolejší, kterou hledáme. Jelikož víme, jak je pole velké, není pro nás problém podívat se na první index (L) a získat hodnotu LL a také na index poslední (R) a získat hodnotu RR. Tyto hodnoty potřebujeme proto, aby vyhledávání bylo přesné. Pole totiž nezačíná vždy lidmi od A a končí lidmi od Z, například zde začínáme s lidmi od B a končíme od V.

Na rovnoběžné ose jsou vyneseny samotné indexy, L a R známe, pod zatím neznámým indexem X se nachází námi hledaná osoba.

Když se podíváme na obrázek, zjistíme, že trojúhelník ABD bude zcela jistě podobný trojúhelníku ACE. Tedy poměr dvou zeleně zvýrazněných stran bude stejný jako poměr dvou oranžově zvýrazněných stran. Dostáváme rovnici (RR - LL) / (XX - LL) = (R - L) / (X - L). Poměr zelených stran jistě známe, protože víme, jak moc se liší vzdálenost od písmena B do písmena D (2) a vzdálenost od B do V (20). Zelený poměr je zde tedy 2:20. Pokud máme pole velké např. 20 prvků, bude hledaný index 2. Pokud třeba 90 prvků, bude hledaný index 9. Nyní již zbývá jen vyjádřit si X. Dostáváme X = L + (R - L) * (XX - LL) / (RR - LL) a máme vyhráno.

Tuto rovnici dosadíme to výpočtu kandidáta (místo původního výpočtu středu v binárním vyhledávání). Musíme si však uvědomit, že zde dělíme neznámou a může nastat situace, kdy bude nulová. Tento případ tedy ošetříme dodatečnou podmínkou. Opět, jako v binárním vyhledávání, se budeme v každém kroku zpřesňovat a hledaný prvek najdeme velmi brzy.

Ohledně časové složitosti je tu malý háček. V průměrném případě sice dostáváme O(log log n), což je jistá výhra oproti O(log n) u binárního vyhledávání. V nejhorším případě se však může stát, že vybereme v každém kroku právě okraj pole a díky tomu tak můžeme zahodit jen jeden jediný prvek. Složitost v nejhorším případě by byla O(n). Rovněž také nastává problém, když bychom do pole chtěli prvky přidávat nebo je z pole mazat, opět to bude díky vlastnostem pole časově nákladné. Algoritmus je tedy vhodný pouze v případě, když nehodláme s prvky v poli moc manipulovat, když máme prvky setříděné a když si jsme jisti, že toto setřídění je rovnoměrné.

Tradičně bude opět následovat zdrojový kód bez rekurze a hned poté verze s rekurzí.

Zdrojový kód - bez rekurze

  • public static int binary_search(int[] array, int item) {
      left = 0;
      right = array.length - 1;
      if ((item < array[left]) || (item > array[right])) // prvek mimo rozsah
        return -1;
      while (left <= right) { // pokud mame co delit
        if (left == right) // ochrana pred delenim nulou
          candidate = left;
        else
          candidate = left + (right - left) * (item - array[left]) / (array[right] - array[left]);
        if (item == array[candidate])
          return candidate; // nalezeno
        else
          if (item < array[candidate]) right = candidate - 1 // vyhodime pravou polovinu
        else
          left = candidate + 1; // vyhodime pravou polovinu
      }
    }
  • public static int binary_search(int[] array, int item) {
      left = 0;
      right = array.length - 1;
      if ((item < array[left]) || (item > array[right])) // prvek mimo rozsah
        return -1;
      while (left <= right) { // pokud mame co delit
         if (left == right) // ochrana pred delenim nulou
          candidate = left;
        else
          candidate = left + (right - left) * (item - array[left]) / (array[right] - array[left]);
        if (item == array[candidate])
          return candidate; // nalezeno
        else
          if (item < array[candidate]) right = candidate - 1 // vyhodime pravou polovinu
        else
          left = candidate + 1; // vyhodime pravou polovinu
      }
    }
  • function binary_search(anarray: array of integer; item: integer): integer;
    begin
      left:=0;
      right:=length(anarray) - 1;
      if ((item < anarray[left]) || (item > anarray[right])) then // prvek mimo rozsah
      begin
        result:=-1;
        exit;
      end;
      while (left <= right) do begin // pokud mame co delit
         if (left = right) then // ochrana pred delenim nulou
          candidate:=left
        else
          candidate:=left + (right - left) * (item - array[left]) / (array[right] - array[left]);
        if (item = anarray[candidate]) then
        begin
          result:=candidate; // nalezeno
          exit;
        end
        else
        if (item < anarray[candidate]) then
          right:=candidate - 1 // vyhodime pravou polovinu
        else
          left:=candidate + 1; // vyhodime pravou polovinu
      end;
    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
        if (left == right) // ochrana pred delenim nulou
          candidate = left
        else
          candidate = left + (right - left) * (item - array[left]) / (array[right] - array[left]);
        end
        if (item == array[candidate])
          return candidate // nalezeno
        else
          if (item < array[candidate])
            right = candidate - 1 // vyhodime pravou polovinu
          else
            left = candidate + 1 // vyhodime pravou polovinu
          end
        end
      end
    end

Zdrojový kód - s rekurzí

  • public static int binary_search(int[] array, int item, int left, int right) {
      if (left > right) return -1
      if (left == right) // ochrana pred delenim nulou
         candidate = left;
       else
         candidate = left + (right - left) * (item - array[left]) / (array[right] - array[left]);
      if (item < array[candidate])
        return binary_search(array, item, left, candidate - 1) // vyhodime pravou polovinu
      if (item > array[candidate])
        return binary_search(array, item, candidate + 1, right) // vyhodime levou polovinu
      return candidate; // nalezeno
    }
  • public static int binary_search(int[] array, int item, int left, int right) {
      if (left > right) return -1
      candidate = (left + right) / 2;
      if (left == right) // ochrana pred delenim nulou
         candidate = left;
       else
         candidate = left + (right - left) * (item - array[left]) / (array[right] - array[left]);
      if (item < array[candidate])
        return binary_search(array, item, left, candidate - 1) // vyhodime pravou polovinu
      if (item > array[candidate])
        return binary_search(array, item, candidate + 1, right) // vyhodime levou polovinu
      return candidate; // nalezeno
    }
  • function binary_search(anarray: array of integer; item, left, right: integer): integer;
    begin
      if (left > right) then begin // nemame co delit
        result:=-1;
        exit;
      end;
      if (left = right) then // ochrana pred delenim nulou
         candidate:=left;
       else
         candidate:=left + (right - left) * (item - array[left]) / (array[right] - array[left]);
      if (item < anarray[candidate]) then
        result:=binary_search(anarray, item, left, candidate - 1) // vyhodime pravou polovinu
      if (item > anarray[candidate]) then
        result:=binary_search(anarray, item, candidate + 1, right) // vyhodime levou polovinu
      if (item == anarray[candidate]) then
        result:=candidate; // nalezeno
    end;
  • def binary_search(array, item, left, right)
      return -1 if (left > right)
      if (left == right) // ochrana pred delenim nulou
         candidate = left
       else
         candidate = left + (right - left) * (item - array[left]) / (array[right] - array[left]);
      end
      if (item < array[candidate])
        return binary_search(array, item, left, candidate - 1) // vyhodime pravou polovinu
      end
      if (item > array[candidate])
        return binary_search(array, item, candidate + 1, right) // vyhodime levou polovinu
      end
      return candidate; // nalezeno
    end

V další lekci, Vyhledávání řetězce v textu, se podíváme na efektivní způsob, jak ve velkých datech vyhledávat řetězec, aneb hledat jehlu v kupce sena.


 

Předchozí článek
Binární vyhledávání
Všechny články v sekci
Vyhledávací algoritmy
Přeskočit článek
(nedoporučujeme)
Vyhledávání řetězce v textu
Článek pro vás napsal David Hartinger
Avatar
Uživatelské hodnocení:
22 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