← Volver a los ejercicios

buscar: la ventana que se encoge

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)mitadlista[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: