Programa de búsqueda de interpolación en C
La búsqueda por interpolación es una variante mejorada de la búsqueda binaria. Este algoritmo de búsqueda trabaja en la posición de sondeo del valor requerido. Para que este algoritmo funcione correctamente, la recopilación de datos debe estar ordenada y distribuida por igual.
Su complejidad en tiempo de ejecución es log2(log2 n).
Implementación en C
#include<stdio.h>
#define MAX 10
// array of items on which linear search will be conducted.
int list[MAX] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
int find(int data) {
int lo = 0;
int hi = MAX - 1;
int mid = -1;
int comparisons = 1;
int index = -1;
while(lo <= hi) {
printf("\nComparison %d \n" , comparisons ) ;
printf("lo : %d, list[%d] = %d\n", lo, lo, list[lo]);
printf("hi : %d, list[%d] = %d\n", hi, hi, list[hi]);
comparisons++;
// probe the mid point
mid = lo + (((double)(hi - lo) / (list[hi] - list[lo])) * (data - list[lo]));
printf("mid = %d\n",mid);
// data found
if(list[mid] == data) {
index = mid;
break;
} else {
if(list[mid] < data) {
// if data is larger, data is in upper half
lo = mid + 1;
} else {
// if data is smaller, data is in lower half
hi = mid - 1;
}
}
}
printf("\nTotal comparisons made: %d", --comparisons);
return index;
}
int main() {
//find location of 33
int location = find(33);
// if element was found
if(location != -1)
printf("\nElement found at location: %d" ,(location+1));
else
printf("Element not found.");
return 0;
}
Si compilamos y ejecutamos el programa anterior, producirá el siguiente resultado:
Salida
Comparison 1
lo : 0, list[0] = 10
hi : 9, list[9] = 44
mid = 6
Total comparisons made: 1
Element found at location: 7
Puede cambiar el valor de búsqueda y ejecutar el programa para probarlo.