Interpolační vyhledávání

Algoritmy Vyhledávání Interpolační vyhledávání

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 článek 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í

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 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 jsiti, že toto setřídění je rovnoměrné.

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

 

Zdrojové kódy jsou v rekonstrukci, děkujeme za pochopení.

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

 

  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?
Ještě nikdo nehodnotil, buď první!


 


Miniatura
Předchozí článek
Binární vyhledávání
Miniatura
Všechny články v sekci
Vyhledávací algoritmy
Miniatura
Následující článek
Binární vyhledávací strom (BST)

 

 

Komentáře

Avatar
Michal Vlasák:

Ahoj,
zajímavý článek. Chápu, že jsou kódy v rekonstrukci. Ale jestli jsem to pochopil dobře, tak interpolační vyhledávání se spíš hodí na textové řetězce, protože vzdálenosti jednotlivých prvků pro získání poměru mi pro čísla přijde zbytečné, tam bych asi volil klasické binární vyhledávání se středem.

Odpovědět 16. května 11:48
"It doesn't work! I hate programming!" - One hour later: "It works! I love programming!"
Avatar
Matěj Kripner
Redaktor
Avatar
Odpovídá na Michal Vlasák
Matěj Kripner:

Nejde o to, co řadíš - interpolační vyhledávání je obecný algoritmus. U čísel je to ale nejjednodušší - jejich "číselnou hodnotu" získáš prostým přečtením, na rozdíl od komplexnějších struktur - třeba řetězců, kde ji musíš obvykle počítat.

Odpovědět 16. května 17:49
"We reject kings, presidents and voting. We believe in rough consensus and running code" David Clark
Avatar
Michal Vlasák:

Pro toho, koho zajímá PHP a vyhledávání řetězců, jsem kód přetvořil. Při automatickém převodu řetězce na číslo docházelo k varování division by zero, takže jsem přidal jednu podmínku.

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8" />
        <title>Interpolační vyhledávání</title>
    </head>
    <body>
        <?php
            function binary_search($array, $item){
                sort($array);
                print_r($array);

                $left = 0;
                $right = count($array) - 1;

                if(($item < $array[$left]) || ($item > $array[$right])){
                    return false;
                }
                while($left <= $right){
                    if($left == $right){
                        $candidate = $left;
                    }
                    /*při převodu textu na číslo docházelo k varování division by zero,
                     *tato podmínka to odstraňuje*/
                    elseif(($array[$right] - $array[$left]) == 0){
                        $candidate = $left;
                    }
                    else{
                        //X = L + (R - L) * (XX - LL) / (RR - LL)
                        $candidate = $left + ($right - $left) * ($item - $array[$left]) / ($array[$right] - $array[$left]);
                    }
                    if($item == $array[$candidate]){
                        settype($candidate, "integer");
                        return $candidate;
                    }
                    else{
                        if($item < $array[$candidate]){
                            $right = $candidate - 1;
                        }
                        else{
                            $left = $candidate + 1;
                        }
                    }
                }
            }

            $technics = array("Novák", "Malý", "Suchar", "Komínek", "Lukáš", "Levý");
            $searched = "Levý";

            $position = binary_search($technics, $searched);
            echo "<br />" . $searched . "  se nachází na pozici " . $position . ".<br />";
        ?>
    </body>
</html>
Odpovědět 17. května 9:25
"It doesn't work! I hate programming!" - One hour later: "It works! I love programming!"
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 3 zpráv z 3.