Modelo por capas

El intervalo y su invariante

Buscas x en un array ordenado a de n valores. Guardas dos índices, bajo y alto, que delimitan la zona donde x todavía podría estar. Al principio, todo el array: bajo = 0, alto = n. El intervalo [bajo, alto) incluye bajo y excluye alto: con alto = n, se mira de la posición 0 a la n − 1.

El invariante (lo que es cierto antes de cada paso):

todo lo que está antes de bajo es menor que xtodo lo que está desde alto en adelante es mayor o igual que x

En la figura, la búsqueda de x = 20 ya avanzó: bajo = 2, alto = 3 y medio = 2. Las posiciones atenuadas, a cada lado, cumplen el invariante.

En cada paso miras el valor del medio del intervalo. Si es menor que x, x no puede estar a su izquierda: bajo pasa a medio + 1. Si no, alto pasa a medio. El intervalo se reduce a la mitad.

Cuando bajo = alto, el intervalo está vacío y bajo es la posición de la primera aparición de x, o donde iría si no está.