Para aquellos de ustedes que no están familiarizados con la búsqueda de interpolación, es un método para buscar un valor en una matriz ordenada que sea potencialmente más rápido que la búsqueda binaria. Observa el primer y el último elemento y (suponiendo que el contenido de la matriz esté distribuido uniformemente) interpola linealmente para predecir la ubicación.

Por ejemplo: tenemos una matriz de longitud 100 con matriz [0] = 0 y matriz [99] = 99. Si buscamos 80, es intuitivo probar la matriz [80] sobre la matriz [50], y si la matriz está cerca de una distribución uniforme, el tiempo de ejecución esperado se reduce alog(log(N))

Para los números, la ubicación a verificar está definida por la ecuación:low + ((toFind - sortedArray[low]) * (high - low + 1)) / (sortedArray[high] - sortedArray[low]).

Un ejemplo común usado para mostrar la naturaleza intuitiva de la búsqueda de interpolación es: imagínese tratando de encontrar la palabra 'amarillo' en un diccionario. No usaría la búsqueda binaria e iría al punto medio. Más bien, irías a la ubicación esperada.

Los humanos pueden interpolar cadenas de forma natural, pero no puedo entender cómo codificarlo. ¿Cómo interpolamos linealmente cadenas?