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.

Absolvováno

Označit lekci jako neabsolvovanou