La búsqueda binaria no persigue a v: encoge
una ventana de candidatos hasta dejar una sola posición, cuidando de no
perder la respuesta por el camino. Ese cuidado es un invariante, y aquí
lo va a encontrar y a demostrar.
1. Antes de ejecutar, prediga
Arreglo y valor:
¿Cuántas veces se parte la ventana antes de quedar en una posición?
2. Ejecute y mire la ventana
Paso 0 de 0
Las posiciones tachadas ya se descartaron y nadie
vuelve a mirarlas. Pruebe el caso con v = 5: el
algoritmo recorre lo mismo y termina en una posición que no es
v.
3. La traza, división por división
[ini..fin)
mitad
lista[mitad]
Decisión
4. Los dos invariantes del while
Al comenzar cada vuelta, ¿qué es siempre
cierto de la ventana lista[ini..fin)? (ese será I₁)
¿Y las cotas de los índices? (ese será I₀)
5. La demostración
Encuentre primero los
dos invariantes en la tarjeta 4. El teorema a demostrar:
Teorema 1 — los invariantes I₀ e I₁ se cumplen.
Inicialización
Las líneas 1–2 dejan ini = 0 y fin = N. Para I₀
se pide 0 ≤ 0 < N ≤ N: la estricta 0 < N vale por la precondición
N ≥ 1 y las otras dos son igualdades. ✓ Para I₁, sustituyendo
ini = 0 y fin = N el lado derecho queda «v está en lista[0..N)», que es
literalmente el lado izquierdo: una equivalencia entre una fórmula y
ella misma. ✓
Estabilidad
Vuelta arbitraria con ini = a y fin = b; como el
cuerpo se ejecuta, b − a > 1, o sea b ≥ a + 2. Primero hay que ver que
la mitad cae estrictamente adentro: de b ≥ a+2 sale a + b ≥ 2a + 2, luego
mitad ≥ a + 1 > a; y de a ≤ b−2 sale a + b ≤ 2b − 2, luego
mitad ≤ b − 1 < b. Con eso las dos ventanas candidatas son no vacías.
Si v < lista[mitad], la línea 6 deja fin = mitad: I₀ pide
0 ≤ a < mitad ≤ N, que ya está probado; e I₁ se conserva porque en
[mitad..b) todo elemento es ≥ lista[mitad] > v, así que ahí no hay
testigos. Si v ≥ lista[mitad], la línea 7 deja ini = mitad, y ese es el
caso de la tarjeta 6. En ambos, los invariantes valen con los valores
nuevos. ✓
Terminación
El ancho fin − ini es un entero positivo por I₀, y
cada vuelta lo deja en mitad − a o en b − mitad, ambos al menos 1 y
estrictamente menores que b − a: un entero positivo que decrece no puede
hacerlo para siempre.
Al salir, la condición fin − ini > 1 es falsa, o sea fin − ini ≤ 1; e
I₀ da ini < fin, o sea fin − ini ≥ 1. Intersectando, fin = ini + 1: la
ventana quedó en una sola posición. Sustituyendo en I₁, el lado derecho es
«v está en lista[ini..ini+1)», un rango de una posición, que vale
exactamente lista[ini] = v. ∎
Teorema 2. La invocación buscar(lista, v) sobre un
arreglo ordenado de tamaño N ≥ 1 responde si v está en el arreglo.
Demostración: es trivial a partir de la correctitud de I₀ e
I₁: la terminación deja fin = ini + 1, y sustituir ese valor en I₁ dice
que la respuesta pedida es lista[ini] = v, que es justo lo que retorna la
línea 8. ∎
6. El caso incómodo
Cuando v ≥ lista[mitad], el algoritmo
se queda con la mitad derecha. Pero v podría estar también en
la izquierda. ¿Por qué no se pierde la respuesta?
7. El costo
Buscar en un arreglo ordenado de n posiciones cuesta: