Saltar al contenido
Omnikalc

Calculadora de pasos de la búsqueda binaria

Introduce el número de elementos ordenados y la duración de una comparación para obtener el número máximo y medio de pasos de una búsqueda binaria y la ganancia respecto a un recorrido lineal.

Actualizado el
Tus datos

Valor fuera de rango

ns

Valor fuera de rango

Resultados

Comparaciones en el peor caso

20

Comparaciones medias para una búsqueda con éxito
18,93
Comparaciones medias para un recorrido lineal
500.001
Duración de una búsqueda binaria (peor caso)
1,000 µs
Duración de un recorrido lineal (media)
25,00 ms
Ganancia en número de comparaciones
26.411 ×

La calculadora de búsqueda binaria da el número máximo y medio de comparaciones necesarias para encontrar un elemento en una lista ordenada, y lo compara con un recorrido lineal.

Cómo se hace el cálculo

  • Introduce el número de elementos ordenados.
  • Introduce la duración de una comparación.
  • La calculadora da los pasos en el peor caso, los pasos medios, la media del recorrido lineal, las duraciones y la ganancia.

Ejemplo

Para 1.000.000 de elementos ordenados, una búsqueda binaria necesita como máximo ⌈log2(1.000.001)⌉ = 20 comparaciones y unas 18,93 de media. Un recorrido lineal necesita 500.000 de media. A 50 ns por comparación, la búsqueda binaria tarda 1,000 µs y el recorrido 25,00 ms, es decir, unas 26.411 veces más comparaciones.

Por qué es útil

La calculadora ayuda a los estudiantes de programación, a los desarrolladores y a quienes se preparan para entrevistas de trabajo a ver por qué la búsqueda logarítmica escala tan bien y a estimar tiempos de búsqueda en arrays y en índices ordenados.

Qué debes saber

La misma idea de dividir a la mitad se aplica a los juegos de adivinar, a la bisección en la depuración, por ejemplo para encontrar qué cambio del código rompió una compilación, y a la búsqueda de raíces. Para saber cuántos intentos hacen falta para identificar un número del 1 al 100, introduce 100 y lee 7 como peor caso. Ten en cuenta que en un equipo real la duración por comparación no es constante: los primeros pasos tocan una memoria en caché, mientras que los últimos, en un array enorme, pueden fallar la caché, así que las duraciones medidas son mayores que la estimación sencilla. Para datos en disco, un árbol de nodos anchos, como un árbol B, hace el trabajo con menos lecturas. Una tabla hash da un tiempo medio constante, pero no conserva el orden.

Herramientas relacionadas

La calculadora de colisiones de hash cubre las tablas hash, la del tamaño de la tabla de páginas muestra otra estructura logarítmica, la del modelo roofline relaciona los movimientos de datos con la velocidad y las de logaritmo calculan directamente el log2.

Preguntas frecuentes

¿Cuántos pasos necesita una búsqueda binaria?

Cada comparación divide a la mitad el rango de candidatos, así que el peor caso es ⌈log2(n + 1)⌉ comparaciones. Para 1 millón de elementos son 20, y para mil millones solo 30. El número aumenta en uno cada vez que la lista se duplica.

¿Cuál es el caso medio?

En una búsqueda con éxito en la que cada elemento es igual de probable, la media es de aproximadamente log2(n) − 1 comparaciones, algo menos que el peor caso, porque la mitad de los elementos están en el nivel más profundo. Una búsqueda sin éxito necesita aproximadamente el número del peor caso.

¿Cuándo es preferible un recorrido lineal?

Para listas muy cortas, de menos de 10 a 20 elementos aproximadamente, un recorrido lineal puede ser igual de rápido o más gracias a un código más sencillo y al comportamiento de la caché. Además, la lista debe estar ordenada, y ordenar cuesta n log n, así que solo compensa si se busca muchas veces.

¿Te ha resultado útil esta calculadora?

¡Gracias por tu opinión!

Resultados orientativos con fines informativos. No sustituyen el consejo de un profesional.