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

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

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

Сложеност 

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

Псеудокод 
Уместо да половимо простор претраге, ми га делимо тако да буде највећа вероватноћа успеха.
  Улаз: 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 := Levi + (z - X[Levi])*(Desni - Levi) / (X[Desni] - X[Levi]);
          if z < X[Srednji] 
             then iNadji := iNadji(z, Levi, Srednji - 1);
          else 
             iNadji := iNadji(z, Srednji, Desni);
  end

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

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

На почетку, лева (L) и десна (D) граница интервала претраге су постављене на почетни и крајњи елемент низа. У овом тренутку, наредни елемент поделе интервала се рачуна на основу следеће формуле:

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

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

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

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

Пошто је 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;
}

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

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

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

Примене 

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

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

Види још 
 Линеарна претрага
 Бинарна претрага
 Хеш табеле
 Низ (структура података)
 Велико О

Референце

Спољашње везе 
 Interpolation search
 National Institute of Standards and Technology
 Interpolation Search - A Log LogN Search

Рачунарство
Алгоритми
Алгоритми претраживања
Seminarski radovi/MATF januar 2014.
У рачунарству , интерполациона претрага је унапређена верзија алгоритма бинарне претраге за претраживање индексираног низа који је уређен по вредности кључа . Базира се на линеарној интерполацији вредности ( кључа ) која се тражи и вредностима на крајевима простора претраге . У литератури се може наћи и термин екстраполациона претрага . Увод У оквиру бинарне претраге простор претраге се сваки пут полови , што гарантује логаритамску временску сложеност . Међутим , ако се у току претраге наиђе на вредност врло блиску траженом броју z , изгледа разумно да се претрага усредсреди на околину тог индекса уместо да се настави са половљењем наслепо . Специјално , ако је вредност z врло мала , може се започети са претрагом негде на почетку низа уместо од средњег индекса . Овај начин претраге може да се упореди са начином на који људи користе речник . Ако тражимо реч која почиње на слово Б , речник ћемо одмах отворити негде близу почетка . Јасно је да у оваквом случају проста бинарна претрага даје лошије резултате . У интерполационо-секвенцијалном претраживању , интерполација се користи да би се лоцирао елемент који је најближи траженом , а затим се користи линеарна претрага за проналажење тачног елемента . У сваком кораку претраге израчунава се у ком простору претраге би кључна вредност могла да се налази . То се извршава на основу вредности на крајевима датог простора претраге и вредности кључа који се тражи . Издвојена вредност кључа се затим упоређује са траженом и уколико нису једнаке , преостали простор претраге се , у зависности од поређења , додатно редукује на део пре или после пронађене вредности . Сложеност Интерполациона претрага је врло ефикасна за улазе са приближно униформно расподељеним елементима . У просеку , сложеност интерполационог алгоритма претраге ( уколико су елементи униформно распоређени ) је О ( log ( log ( n ) ) ) , где је n број елемената низа који се претражује . У најгорем случају ( на пример , уколико нумеричка вредност кључа расте експоненцијално ) број поређења може достићи и ред величине O ( n ) . Псеудокод Уместо да половимо простор претраге , ми га делимо тако да буде највећа вероватноћа успеха . Улаз : X ( низ од n неопдајуће уређених бројева ) i z ( број који се тражи ) . Излаз : Poz ( индекс i такав да је X[ i ] = z , iliако такав индекс не постоји ). begin if z < X[ 1 ] or z > X[ n ] then Poz\:={ неуспешна претрага } else Poz \ := iNadji( z , 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 \ := else Srednji \ := Levi + ( z - X[ Levi ] ) *( Desni - Levi ) / ( X[ Desni ] - X[ Levi ] ) ; if z < X[ Srednji ] then iNadji \ := iNadji( z , Levi , Srednji - else iNadji \ := iNadji( z , Srednji , Desni ) ; end Пример Кратак пример који илуструје операције интерполационе претраге . Тражи се вредност v =у следећем низу : На почетку , лева ( L ) и десна ( D ) граница интервала претраге су постављене на почетни и крајњи елемент низа . У овом тренутку , наредни елемент поделе интервала се рачуна на основу следеће формуле : Специјално за дати низ ( црвено = простор претраге , плаво = x , болдовано = тражени елемент ) : Затим се вредност елемента x упоређује са траженом вредношћу . Ако су једнаке ту је крај , јер је пронађена вредност . У супротном се подешавају границе простора претраге . Ако је x мање , то значи да морамо да гледамо десно , односно подешавамо вредност леве границе на x+1 , у супротном десна граница добија вредност x-1 . Пошто је у нашем случају вредност A[ 2 ] =мања од тражене , постављамо леву границу на L = x+1 = Десна граница не мења своју вредност и формула за следећи елемент поделе новог интервала има следећи облик : Сада , наш низ изгледа овако : Пошто је A[ x ] = A[ 3 ] == v , следи да је тражена вредност пронађена и прекида се извршавање алгоритма . Имплементација Имплементација једноставне верзије интерполационог алгоритма претраге . C / * Funkcija trazi u sortiranom nizu a [ ] duzine n broj x . * Vraca indeks pozicije проnadjenog elementa * iliako element nije pronadjen * / int interpolaciona_pretraga( int a [ ] , int n , int x ) { int l = int d = n - 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 / * 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 - / * Ako je sredisnji element manji od x , tada se x mora nalaziti u desnoj polovini niza * / else if ( x > a[ s ] ) l = s + else / * Ako je sredisnji element jednak x , tada smo pronasli x na poziciji s * / return s ; } / * ako nije pronadjen vraca * / return } Прилагођавање различитим скуповима података Када су кључеви за сортирање униформно распоређени бројеви , линеарна интерполација се имплементира релативно једноставно и проналази индекс који је врло близу тражене вредности . Са друге стране , за телефонски именик сортиран по презименима , такав начин имплементације интерполационе претраге не може да се примени . Неки принципи високог нивоа ипак и даље важе - нпр. могуће је проценити позицију траженог уноса у именику користећи релативну фреквенцију слова . Неке имплементације интерполационе претраге не раде на задовољавајући начин ако се примене на скуп података који поседује низ једнаких вредности кључева . Најједноставнија имплементација интерполационе претраге неће нужно изабрати први ( или последњи ) елемент у таквом низу . Примене Пре него што се одлучимо за овај алгоритам претраге треба имати на уму да је код избора наредног индекса потребно извршити нешто компликованије аритметичке операције . Ова врста претраге може бити корисна за проналажење одређеног податка у великој сортираној датотеци на диску , где свако поређење подразумева претраживање диска , што је много скупље од интерполационе аритметике . Индексиране структуре података као што је Б-стабло такође редукују број приступа диску , и чешће се користе за индексирање података на тврдим дисковима , делом зато што могу да обрађују различите типове података и имају могућност онлајн ажурирања . Међутим , интерполациона претрага може бити корисна ако је потребно претражити сортиран , али неиндексиран скуп великих датотека . Види још Линеарна претрага Бинарна претрага Хеш табеле Низ ( структура података ) Велико О Референце Спољашње везе Interpolation search National Institute of Standards and Technology Interpolation Search - A Log LogN Search Рачунарство Алгоритми Алгоритми претраживања Seminarski radovi / MATF januar