Búsqueda Binaria

🔍 Búsqueda Binaria

La búsqueda binaria nos permite encontrar un elemento en un arreglo ordenado en tiempo:

\[ O(\log n) \]

Imagina que tenemos este arreglo ordenado con 10 elementos:

[ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 ] 

Queremos encontrar el número 10.

Paso 1

[ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 ]

Miramos el elemento central: 5.

Queremos buscar el 10.

Como 5 < 10, descartamos la mitad izquierda.

Paso 2

[ 6 | 7 | 8 | 9 | 10 ]

Nuevo centro: 8.

8 < 10 → descartamos la mitad izquierda.

Paso 3

[ 9 | 10 ]

Nuevo centro: 9.

9 < 10 → descartamos la izquierda.

Paso 4 🎯

[ 10 ]

¡Encontramos el valor buscado! 🚀

📊 Complejidad

Con búsqueda binaria en un arreglo de tamaño \(n\), el número de pasos máximo es:

\[ \log_2(n) \]

Ejemplo: con 1 millón de elementos → solo 19 comparaciones.