Interpolačnou vyhľadávanie
Interpolačnou vyhľadávania je algoritmus veľmi podobný binárnemu vyhľadávanie a používa sa pri vyhľadávaní na zotriedené poli v prípade, že vieme, že sú dáta rovnomerne rozložená. Nasledujúci text bude teda nadväzovať na článok binárne vyhľadávanie. V kóde sa tieto dva algoritmy líšia v podstate len na jednom riadku, a to je výber kandidáta, teda prvku, o ktorom si myslíme, že by mohol byť tým, čo hľadáme. V binárnom vyhľadávania bol tento prvok vždy stred poľa.
Ak si ale sme istí, že dáta v našom poli sú rovnomerne rozložená, je úplne zbytočné pozerať sa do stredu, keď môžeme byť oveľa presnejšie. Ak by sme opäť hľadali medzi zamestnancami, ale tentoraz podľa mena a hľadali by sme pána Emila Zlého, je nám jasné, že nemá zmysel pozerať sa doprostred, pretože ľudia od Z budú určite niekde ku koncu. Ak by sme hľadali pani Dolejší, bude niekde kúsok od začiatku.
Ako zistíme, v ktorom mieste máme prvok hľadať? Využijeme totiž pomerov a aby bola celá situácia ešte prehľadnejšie, zakreslil som ju cez podobnosť trojuholníkov.
Ako je vidieť, na zvislú os sú nanesené hodnoty v poli. LL je hodnota na ľavom indexu v poli, môže to byť napríklad pani Bartošková. RR je hodnota na najpravejšom indexu, tou môže byť napríklad pán Vendelín. Hodnota XX je pani Dolejší, ktorú hľadáme. Keďže vieme, ako je pole veľké, nie je pre nás problém pozrieť sa na prvý index (L) a získať hodnotu LL a tiež na index posledný (R) a získať hodnotu RR. Tieto hodnoty potrebujeme preto, aby vyhľadávanie bolo presné. Pole totiž nezačína vždy ľuďmi od A a končí ľuďmi od Z, napríklad tu začíname s ľuďmi od od B a končíme od V.
Na rovnobežné osi sú nanesené samotné indexy, L a R poznáme, pod zatiaľ neznámym indexom X sa nachádza nami hľadaná osoba.
Keď sa pozrieme na obrázok, zistíme, že trojuholník ABD bude celkom iste podobný trojuholníka ACE. Teda pomer dvoch zelene zvýraznených strán bude rovnaký ako pomer dvoch oranžovo zvýrazněnách strán. Dostávame rovnicu (RR - LL) / (XX - LL) = (R - L) / (X - L). Pomer zelených strán iste poznáme, pretože vieme, ako veľmi sa líši vzdialenosť od písmena B do písmená D (2) a vzdialenosť od B do V (20). Zelený pomer je tu teda 2:20. Ak máme pole veľké napr. 20 prvkov, bude hľadaný index 2. Ak treba 90 prvkov, bude hľadaný index 9. Teraz už zostáva len vyjadriť si X. Dostávame X = L + (R - L) * (XX - LL) / ( RR - LL) a máme vyhrané.
Túto rovnicu dosadíme to výpočtu kandidáta (namiesto pôvodného výpočtu stredu v binárnom vyhľadávania). Musíme si však uvedomiť, že tu delíme neznámu a môže nastať situácia, kedy bude nulová. Tento prípad teda ošetríme dodatočnú podmienkou. Opäť, ako v binárnom vyhľadávania, sa budeme v každom kroku spresňovať a hľadaný prvok nájdeme veľmi skoro.
Ohľadom časovej zložitosti je tu malý háčik. V priemernom prípade síce dostávame O (log log n), čo je istá výhra oproti O (log n) u binárneho vyhľadávania. V najhoršom prípade sa však môže stať, že vyberieme v každom kroku práve okraj poľa a vďaka tomu tak môžeme zahodiť len jeden jediný prvok. Zložitosť v najhoršom prípade by bola O (n). Rovnako tiež nastáva problém, keď by sme do poľa chceli prvky pridávať alebo ich z poľa mazať, opäť to bude vďaka vlastnostiam pole časovo nákladné. Algoritmus je teda vhodný iba v prípade, keď nehodláme s prvkami v poli moc manipulovať, keď máme prvky zotriedené a keď si sme jsiti, že toto zotriedenie je rovnomerné.
Tradícia bude opäť nasledovať zdrojový kód bez rekurzie a hneď potom verzie s rekurziu.
Zdrojové kódy sú v rekonštrukcii, ďakujeme za pochopenie.
Zdrojový kód - bez rekurzia
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 rekurziu
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
David sa informačné technológie naučil na Unicorn University - prestížnej súkromnej vysokej škole IT a ekonómie.