Recorrido narrado

Buscar algo que no está

Buscas 20 en [3, 8, 15, 21, 30, 42, 57].

1. [0, 7), medio 3: 21 no es menor que 20, alto ← 3.
2. [0, 3), medio 1: 8 es menor que 20, bajo ← 2.
3. [2, 3), medio 2: 15 es menor que 20, bajo ← 3.
4. [3, 3): vacío. Devuelve 3.

En la figura están los cuatro pasos; lo atenuado es lo que la búsqueda ya descartó.

La posición 3 tiene 21, que no es 20: el valor no está. Pero 3 es justo donde habría que insertarlo para mantener el orden. Por eso esta versión devuelve una posición y no «sí o no»: quien llama comprueba si bajo < longitud(a) y a[bajo] = x.

En cada paso el intervalo se reduce a la mitad. Con n valores, como mucho ⌈log₂(n + 1)⌉ comparaciones: 20 para un millón. Es O(log n) en el peor caso, si el array está ordenado.

Su fila en la tabla de costos

La búsqueda binaria abre la tabla de conjunto y diccionario, con el array sin ordenar como alternativa simple:

Representación	buscar(k)
array sin ordenar	O(n), peor caso
array ordenado	O(log n), peor caso, si está ordenado y se lee cualquier posición en O(1)