Implementazione in C, dell’algoritmo di RICERCA INTERPOLATA. Per array ordinati.

A differenza di quella Binaria che divide in 2 l’array, la ricerca interpolata, sfruttando una formula (infatti funziona solo su array ordinati e con elementi equidistribuiti) cerca di avvicinarsi il più possibile all’elemento che cerchiamo. Se l’array è parecchio equidistribuito si arriva ad una complessità computazionale pari a O(log(logN)). Altrimenti se così non fosse, questo algoritmo può Degenerare nella ricerca sequenziale e quindi arrivare fino ad una complessità computazionale lineare del tipo O(n).

formula per la prossimità di un elemento: prox = inf + (sup – inf)*(x – a[inf].chiave) / (a[sup].chiave – a[inf].chiave);

//RICERCA INTERPOLATA
int Ricerca_interpolata(t_id_attrib a[], int n, long int x){
int inf = 0, sup = n-1, prox;
 
while ((a[inf].chiave <= x) && (a[sup].chiave >= x)){
prox = inf + (sup - inf)*(x - a[inf].chiave) / (a[sup].chiave - a[inf].chiave); //formula da dimostrare.
 
if (a[prox].chiave == x) return prox;
else if (x > a[prox].chiave) inf = prox + 1;
else if (x < a[prox].chiave) sup = prox - 1;
else return -1;
 
}
 
return -1;
 
}