Căutare interpolare

Căutare interpolare
Clasă	Algoritm de căutare
Structură de date	Comandat de matrice
Cel mai rău caz din punct de vedere temporal	n
Caz optim în timp	1
Caz mediu în timp	jurnal (jurnal ( n ))
Manual

Căutarea prin interpolare este un algoritm pentru a căuta o anumită valoare cheie într-o matrice sortată după aceleași valori cheie. Este metoda corespunzătoare pentru a căuta un anumit termen într-un dicționar sau pentru un nume într-un director telefonic .

La fiecare pas al căutării, algoritmul evaluează unde poate fi elementul în spațiul de căutare pe baza valorilor tastelor de la capetele matricei și a valorii de căutat. Apoi compară cheia selectată cu valoarea de căutat. Dacă este valoarea solicitată, atunci algoritmul este terminat. În caz contrar, spațiul de căutare este înlocuit cu partea stângă sau dreaptă rămasă a matricei, în funcție de rezultatul comparației.

Căutarea prin interpolare poate fi considerată ca o generalizare a cercetării dihotomice ; acesta din urmă, de fapt, urmează aceeași procedură, dar nu se bazează pe valorile extreme, ci întotdeauna tăie spațiul de căutare în jumătate.

În medie, costul algoritmului este log (jurnal ( n )) comparații (unde n este dimensiunea matricei), dar este eficient numai dacă cheile sunt distribuite în mod rezonabil, adică dacă diferența dintre două valori contigue este aproape constant. În cel mai rău caz (de exemplu, dacă valoarea numerică a tastelor crește exponențial), vor exista comparații O ( n ). ^[1] ^[2] ^[3]

Exemplu de implementare

Următorul cod C ++ este un exemplu de implementare simplă. La fiecare pas calculează o posibilă poziție a valorii și apoi restricționează intervalul - ca în căutarea binară - prin creșterea limitei inferioare sau scăderea limitei superioare.

 șablon < typename T >
int interpolation_search ( T arr [], dimensiunea int , tasta T )
{
    int low = 0 ;
    int ridicat = dimensiune - 1 ;
    int mid ;

    while ( arr [ high ] ! = arr [ low ] && key > = arr [ low ] && key <= arr [ high ]) {
        mid = low + ( key - arr [ low ]) * (( high - low ) / ( arr [ high ] - arr [ low ]));

        if ( arr [ mid ] < tastă )
            scăzut = mijloc + 1 ;
        else if ( tasta < arr [ mid ])
            ridicat = mijlociu - 1 ;
        altceva
            întoarce-te la mijloc ;
    }
    if ( tasta == arr [ low ])
        reveniți jos ;
    altceva
        retur -1 ;
}

Notă

^ Weiss, Mark Allen (2006). Structuri de date și rezolvarea problemelor folosind Java , Pearson Addison Wesley
^ Armenakis, AC, Garey, LE, Gupta, RD, O adaptare a unei metode de găsire a rădăcinii la căutarea fișierelor de disc ordonate, BIT Numerical Mathematics, Volumul 25, Numărul 4 / Decembrie, 1985.
^ Sedgewick, Robert (1990), Algorithms in C , Addison-Wesley