¿Cuál es la complejidad temporal de la búsqueda binaria en un array ordenado?
Opciones
- O(1)
- O(log n) (Opción correcta)
- O(n)
- O(n log n)
Respuesta
O(log n)
Por qué
La búsqueda binaria mira el elemento central. Si el objetivo es menor, descarta la mitad derecha; si es mayor, la izquierda. Luego repite con lo que queda.
Cada paso reduce a la mitad los elementos restantes: 1.000.000 → 500.000 → 250.000 ... así que solo necesita unos 20 pasos. Eso es O(log n).
Solo funciona con datos ORDENADOS. Python la tiene en el módulo bisect.
Recuerda
Reducir a la mitad en cada paso = O(log n).