Complejidad Temporal
Mejor: O(1)
Prom: O(log log n)
Peor: O(n)
Interpolation Search es una variante mejorada de Binary Search para datos ordenados uniformemente distribuidos. En lugar de ir siempre al medio, estima la posición del objetivo basándose en su valor.
Cómo funciona:
1. Estimar posición: pos = low + ((objetivo - arr[low]) × (high - low)) / (arr[high] - arr[low])
2. Si arr[pos] es igual al objetivo, retornar pos
3. Si arr[pos] < objetivo, buscar en la porción derecha
4. Si arr[pos] > objetivo, buscar en la porción izquierda
Complejidad Temporal:
Mejor: O(1)
Promedio: O(log log n) — para distribución uniforme
Peor: O(n) — para distribución no uniforme
Complejidad Espacial: O(1)
Propiedades:
- Requiere arreglo ordenado
- Mejor para datos uniformemente distribuidos
- Puede degradarse a O(n) para distribuciones sesgadas
Interpolation Search puede ser significativamente más rápida que Binary Search cuando los datos están uniformemente distribuidos, ya que hace mejores estimaciones sobre dónde podría estar el objetivo.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Interpolation Search (Búsqueda por Interpolación)?
- Interpolation Search es una variante mejorada de Binary Search para datos ordenados uniformemente distribuidos. En lugar de ir siempre al medio, estima la posición del objetivo basándose en su valor.
- ¿Cuál es la complejidad de Interpolation Search (Búsqueda por Interpolación)?
- Tiempo (promedio): O(log log n) — para distribución uniforme · Espacio: O(1)
- ¿Para quién es este visualizador de Interpolation Search (Búsqueda por Interpolación)?
- La visualización de Interpolation Search (Búsqueda por Interpolación) está pensada para nivel intermedio, dentro de la categoría Búsqueda. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Interpolation Search (Búsqueda por Interpolación)?
- En la misma categoría (Búsqueda) puedes explorar: Binary Search, Linear Search, Jump Search. Todos tienen visualización interactiva.