Cómo funciona
Solo sirve con datos ordenados. Se mantiene un rango de candidatos, de lo a hi, y se
mira el del medio, mid. Si es el buscado, se termina. Si es menor, el buscado solo puede estar a su
derecha y toda la mitad izquierda se descarta de golpe (lo ← mid + 1); si es mayor, se
descarta la derecha (hi ← mid − 1). Cuando lo supera a hi, no quedan candidatos: no está.
Cada vuelta hace una comparación con tres resultados posibles (igual, menor o mayor) y la cuenta como
una sola.
Paso a paso: buscar 7 en [1, 3, 5, 7, 9, 11]
- 01lo = 0, hi = 5: mid = 2, A[2] = 5 < 7. Se descartan el 1, el 3 y el 5: lo ← 3.
- 02lo = 3, hi = 5: mid = 4, A[4] = 9 > 7. Se descartan el 9 y el 11: hi ← 3.
- 03lo = hi = 3: mid = 3, A[3] = 7. Encontrado tras 3 comparaciones; la búsqueda lineal habría necesitado 4.
- 04Buscando el 6: los dos primeros pasos son iguales, pero A[3] = 7 > 6, así que hi ← 2. Ahora lo = 3 > hi = 2: no está, también tras 3 comparaciones.
Por qué log₂ n
Cada comparación deja, como mucho, la mitad de los candidatos. Con n números, tras k comparaciones
quedan unos n / 2ᵏ, así que bastan ⌈log₂(n + 1)⌉ comparaciones en el peor caso: 3 para 6 números, 6
para 60 y 20 para un millón. Doblar los datos solo cuesta una comparación más.
Complejidad
- Mejor caso
- O(1)
- Caso promedio
- O(log n)
- Peor caso
- O(log n)
- Espacio extra
- O(1)
- Requisito
- Datos ordenados
- Acceso
- Por posición