Интерполациона претрага

У рачунарству, интерполациона претрага је унапређена верзија алгоритма бинарне претраге за претраживање индексираног низа који је уређен по вредности кључа. Базира се на линеарној интерполацији вредности (кључа) која се тражи и вредностима на крајевима простора претраге. У литератури се може наћи и термин екстраполациона претрага.

Увод[уреди | уреди извор]

У оквиру бинарне претраге простор претраге се сваки пут полови, што гарантује логаритамску временску сложеност. Међутим, ако се у току претраге наиђе на вредност врло блиску траженом броју z, изгледа разумно да се претрага усредсреди на околину тог индекса уместо да се настави са половљењем наслепо. Специјално, ако је вредност z врло мала, може се започети са претрагом негде на почетку низа уместо од средњег индекса.^[1]

Овај начин претраге може да се упореди са начином на који људи користе речник. Ако тражимо реч која почиње на слово Б, речник ћемо одмах отворити негде близу почетка. Јасно је да у оваквом случају проста бинарна претрага даје лошије резултате. У интерполационо-секвенцијалном претраживању, интерполација се користи да би се лоцирао елемент који је најближи траженом, а затим се користи линеарна претрага за проналажење тачног елемента. У сваком кораку претраге израчунава се у ком простору претраге би кључна вредност могла да се налази. То се извршава на основу вредности на крајевима датог простора претраге и вредности кључа који се тражи. Издвојена вредност кључа се затим упоређује са траженом и уколико нису једнаке, преостали простор претраге се, у зависности од поређења, додатно редукује на део пре или после пронађене вредности.

Сложеност[уреди | уреди извор]

Интерполациона претрага је врло ефикасна за улазе са приближно униформно расподељеним елементима.^[1] У просеку, сложеност интерполационог алгоритма претраге (уколико су елементи униформно распоређени) је О (log (log (n))), где је n број елемената низа који се претражује. У најгорем случају (на пример, уколико нумеричка вредност кључа расте експоненцијално) број поређења може достићи и ред величине O (n).^[2]

Псеудокод[уреди | уреди извор]

Уместо да половимо простор претраге, ми га делимо тако да буде највећа вероватноћа успеха.^[1]

 Улаз: X (низ од n неопдајуће уређених бројева) i z (број који се тражи).
 Излаз: Poz (индекс i такав да је X[i] = z, ili 0 ако такав индекс не постоји).

 begin
    if z < X[1] or z > X[n] 
       then Poz := 0 {неуспешна претрага}
    else 
       Poz := iNadji(z, 1, n);
 end
 function iNadji(z; Levi;Desni) : integer
 begin
      if X[Levi] = z 
         then i_Nadji := Levi;
      else if Levi = Desni or X[Levi] = X[Desni] 
         then iNadji := 0;
      else 
         Srednji :=  $\lfloor$ Levi + (z - X[Levi])*(Desni - Levi) / (X[Desni] - X[Levi]) $\rfloor$ ;
         if z < X[Srednji] 
            then iNadji := iNadji(z, Levi, Srednji - 1);
         else 
            iNadji := iNadji(z, Srednji, Desni);
 end

Пример[уреди | уреди извор]

Кратак пример који илуструје операције интерполационе претраге.

Тражи се вредност v = 7 у следећем низу:

2	4	7	9	12	21	26	31	37

На почетку, лева (L) и десна (D) граница интервала претраге су постављене на почетни и крајњи елемент низа. У овом тренутку, наредни елемент поделе интервала се рачуна на основу следеће формуле: $x=l+{\frac {v-A[l]}{A[d]-A[l]}}\cdot (d-l)$

Специјално за дати низ (црвено = простор претраге, плаво = x, болдовано = тражени елемент):

$x=1+{\frac {7-2}{37-2}}\cdot (9-1)\approx 2,15\to 2$

2	4	7	9	12	21	26	31	37

Затим се вредност елемента x упоређује са траженом вредношћу. Ако су једнаке ту је крај, јер је пронађена вредност. У супротном се подешавају границе простора претраге. Ако је x мање, то значи да морамо да гледамо десно, односно подешавамо вредност леве границе на x+1, у супротном десна граница добија вредност x-1.

Пошто је у нашем случају вредност A[2] = 4 мања од тражене, постављамо леву границу на L = x+1 = 3. Десна граница не мења своју вредност и формула за следећи елемент поделе новог интервала има следећи облик:

$x=3+{\frac {7-7}{37-7}}\cdot (9-3)=3\to 3$

Сада, наш низ изгледа овако:

2	4	7	9	12	21	26	31	37

Пошто је A[x] = A[3] = 7 = v, следи да је тражена вредност пронађена и прекида се извршавање алгоритма.

Имплементација[уреди | уреди извор]

Имплементација једноставне верзије интерполационог алгоритма претраге.

C[уреди | уреди извор]

/* Funkcija trazi u sortiranom nizu a[] duzine n broj x. 
 * Vraca indeks pozicije проnadjenog elementa 
 * ili -1 ako element nije pronadjen */

int interpolaciona_pretraga(int a[], int n, int x)
{
    int l = 0;
    int d = n - 1;
    int s;

    /* sve dok je indeks l levo od indeksa d  */
    while (l <= d) {

	/* Ako je element manji od pocetnog ili veci od poslednjeg clana
           u delu niza a[l],...,a[d], tada nije u tom delu niza.
	 Provera je neophodna, da se ne bi izaslo izvan opsega indeksa [l,d] */
	if (x < a[l] || x > a[d])
	 return -1;

	/* U suprotnom, x je izmedju a[l] i a[d], 
           ako a[l]==a[d] tada je x jednako ovim vrednostima, pa vracamo indeks l (ili d).
           Provera je neophodna, zbog potencijalnog deljenja nulom pri izracunavanju s. */
	else if (a[l] == a[d])
	 return l;

	/* Racunamo sredisnji indeks */
	s = l + ((double) (x - a[l]) / (a[d] - a[l])) * (d - l);

	/* Ako je sredisnji element veci od x, 
           tada se x mora nalaziti u levoj polovini niza */
	if (x < a[s])
	 d = s - 1;

	/* Ako je sredisnji element manji od x,
	 tada se x mora nalaziti u desnoj polovini niza */
	else if (x > a[s])
	 l = s + 1;

	else
	 /* Ako je sredisnji element jednak x, 
	 tada smo pronasli x na poziciji s */
	 return s;
    }

    /* ako nije pronadjen vraca -1 */
    return -1;
}

Прилагођавање различитим скуповима података[уреди | уреди извор]

Када су кључеви за сортирање униформно распоређени бројеви, линеарна интерполација се имплементира релативно једноставно и проналази индекс који је врло близу тражене вредности. Са друге стране, за телефонски именик сортиран по презименима, такав начин имплементације интерполационе претраге не може да се примени. Неки принципи високог нивоа ипак и даље важе - нпр. могуће је проценити позицију траженог уноса у именику користећи релативну фреквенцију слова.

Неке имплементације интерполационе претраге не раде на задовољавајући начин ако се примене на скуп података који поседује низ једнаких вредности кључева. Најједноставнија имплементација интерполационе претраге неће нужно изабрати први (или последњи) елемент у таквом низу.

Примене[уреди | уреди извор]

Пре него што се одлучимо за овај алгоритам претраге треба имати на уму да је код избора наредног индекса потребно извршити нешто компликованије аритметичке операције. Ова врста претраге може бити корисна за проналажење одређеног податка у великој сортираној датотеци на диску, где свако поређење подразумева претраживање диска, што је много скупље од интерполационе аритметике.

Индексиране структуре података као што је Б-стабло такође редукују број приступа диску, и чешће се користе за индексирање података на тврдим дисковима, делом зато што могу да обрађују различите типове података и имају могућност онлајн ажурирања. Међутим, интерполациона претрага може бити корисна ако је потребно претражити сортиран, али неиндексиран скуп великих датотека.