- Valor buscado
- Aún posibles
- Comparadas
- Descartadas
- Encontradas
Búsqueda exponencial
La búsqueda exponencial encuentra un valor en una lista ordenada en dos fases. Primero mira las posiciones 1, 2, 4, 8, 16 y así sucesivamente, duplicando cada vez, hasta que el valor allí no sea menor que el valor buscado. Luego aplica búsqueda binaria al tramo entre las dos últimas posiciones. Elige el valor que quieres buscar y descubre por qué los valores cercanos al principio se encuentran con muy pocas comparaciones. Pulsa Reproducir para ver la búsqueda, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. La línea discontinua marca el valor que buscas, y la parte sombreada es donde aún puede estar. La búsqueda exponencial necesita una lista ordenada, así que una lista desordenada se ordena primero. Elige el valor, cuántas barras hay, o escribe tus propios números. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Elige el valor que quieres buscar y cuántas barras hay. O escribe tus propios números: la búsqueda exponencial los ordena primero.
- Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto de la búsqueda.
- Busca un valor cercano al principio y otro cercano al final, y compara el recuento con «La búsqueda binaria necesitaría».
Cómo funciona la búsqueda exponencial
Mira el valor de la posición 1. Si es menor que el valor buscado, mira la posición 2, luego la 4, 8, 16, duplicando cada vez. En cuanto un valor no sea menor, para: el valor buscado solo puede estar después de la posición mirada antes y antes de esta. Aplica búsqueda binaria a ese tramo. Si al duplicar te pasas del final de la lista, aplica búsqueda binaria desde la última posición mirada hasta el final.
Rápida al principio, sin conocer la longitud
Para llegar a un valor en la posición i, la duplicación necesita unas log₂ i consultas, y el tramo que encuentra tiene menos de i valores, así que la búsqueda binaria necesita unas log₂ i más. En total son unas 2 log₂ i, que dependen de dónde está el valor buscado, no de lo larga que sea la lista. Los valores cercanos al principio se encuentran antes que con la búsqueda binaria simple; los cercanos al final cuestan hasta el doble, aproximadamente. Como nunca necesita la longitud de la lista, también funciona con listas demasiado largas para medirlas o sin un final conocido.
Preguntas frecuentes
¿Cómo funciona la búsqueda exponencial?
En una lista ordenada revisa las posiciones 1, 2, 4, 8 y así sucesivamente hasta que el valor allí no sea menor que el valor buscado. Entonces el valor buscado solo puede estar entre las dos últimas posiciones revisadas, y una búsqueda binaria en ese tramo lo encuentra.
¿Es la búsqueda exponencial más rápida que la búsqueda binaria?
Cuando el valor buscado está cerca del principio de la lista, sí: necesita unas 2 log₂ i comparaciones para un valor en la posición i, sea cual sea la longitud de la lista. Cuando está cerca del final, la búsqueda binaria simple es más rápida, hasta el doble, aproximadamente.
¿Para qué se usa?
Para buscar en listas de longitud desconocida o ilimitada, como un flujo o una secuencia infinita, y para fusionar secuencias ordenadas, donde la siguiente coincidencia suele estar cerca. El modo galope de Timsort usa la misma idea de duplicar.
¿Por qué se llama exponencial?
Porque las posiciones que revisa crecen de forma exponencial: 1, 2, 4, 8, 16, cada una el doble de la anterior. También se llama búsqueda por duplicación o búsqueda galopante.
¿Se envían mis números a algún sitio?
No. La búsqueda se ejecuta en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor