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.