La búsqueda binaria de la clase encuentra el borde entre
las posiciones que no cumplen una propiedad y las que sí. El código ya está
escrito y no cambia; lo que hay que aportar en cada problema nuevo es la
propiedad. Aquí el arreglo ni siquiera está ordenado, y aun así se puede.
1. La especificación y la predicción
Entrada: un arreglo A[0..N) de N ≥ 1
números distintos que resulta de tomar un arreglo ordenado de forma
creciente y rotarlo k posiciones hacia la izquierda, de modo que A queda
formado por dos tramos crecientes, el primero con los valores grandes y el
segundo con los pequeños. Salida: la posición del mínimo, que
es justo donde empieza el segundo tramo.
Arreglo:
¿En qué posición está el mínimo?
2. Ejecute y mire la ventana
Paso 0 de 0
Debajo de cada casilla, lo que la comparación de la
línea 6 diría de ella: grande si A[t] > A[N−1],
pequeño si no. Mire cómo quedan repartidas.
3. La traza, división por división
[l..r)
mitad
A[mitad]
¿A[mitad] > A[N−1]?
Decisión
4. El predicado
La búsqueda binaria de un borde necesita una
propiedad p(t) que sea monótona: falsa en un tramo inicial y
verdadera de ahí en adelante, sin volver atrás. El borde es la primera
posición donde se vuelve verdadera.
¿Cuál de estas es monótona sobre este arreglo?
5. Los invariantes
Encuentre primero el
predicado en la tarjeta 4.
¿Qué se cumple en cada chequeo de la línea 4? (ese será I₁)
¿Y las cotas? (ese será I₀)
6. La demostración
Complete la tarjeta 5.
El teorema a demostrar: Teorema 1 — los invariantes I₀ e I₁ se
cumplen.
Inicialización: con l = 0 y r = N, ¿por qué se cumple I₁?
I₀: 0 ≤ 0 ≤ N ≤ N. ✓ I₁ afirma dos cosas,
una sobre las posiciones a la izquierda de l y otra sobre las que están
en r o más allá. Con l = 0 y r = N los dos conjuntos son vacíos y las dos
afirmaciones se cumplen sin exigir nada. ✓ Arrancar con la ventana
completa es arrancar sin haber decidido nada, y eso es justo lo que dice
el invariante.
Estabilidad: en la rama de la línea 7 se hace l = mitad + 1. ¿Qué hay que justificar?
Se toma un chequeo arbitrario con l < r y se
asumen I₀ e I₁.
Rama de la línea 7, con A[mitad] > A[N−1]: hay que ver que toda
posición t < mitad + 1 cumple A[t] > A[N−1]. Para t < l se tiene
por I₁. Para l ≤ t ≤ mitad hace falta el predicado: como p es monótona y
p(mitad) es falso, p(t) es falso para todo t ≤ mitad, o sea
A[t] > A[N−1]. ✓ La mitad derecha de I₁ no se toca porque r no cambia. ✓
Rama de la línea 8, con A[mitad] ≤ A[N−1]: hay que ver que toda
posición t ≥ mitad cumple A[t] ≤ A[N−1]. Para t ≥ r se tiene por I₁, y
para mitad ≤ t < r sale otra vez de la monotonía: p(mitad) es
verdadero, luego p(t) también. ✓
I₀ se mantiene en las dos ramas porque l ≤ mitad < r: en la primera
l crece sin pasarse de r, y en la segunda r baja sin bajar de l. Y el
ciclo avanza, porque en las dos la ventana se acorta al menos en una
posición. ✓
Terminación: el ciclo sale con l = r. ¿Por qué esa posición es la del mínimo?
La condición rota da l ≥ r y I₀ da l ≤ r:
intersecando, l = r. Sustituyendo en I₁: toda posición t < l cumple
A[t] > A[N−1] y toda posición t ≥ l cumple A[t] ≤ A[N−1]. Es decir, l
es la primera posición del segundo tramo, y como ese tramo es creciente,
su primer elemento es el mínimo de todo el arreglo. Además l ≤ N−1,
porque la posición N−1 cumple el predicado y por lo tanto no puede haber
quedado a la izquierda de l: el valor devuelto siempre es un índice
válido. ∎
Teorema 2. La invocación posicionDelMinimo(A) sobre
un arreglo rotado de N ≥ 1 elementos distintos devuelve la posición de su
mínimo, en Θ(lg N). Demostración: por el Teorema 1 los invariantes
se cumplen; la terminación deja l = r y sustituir en I₁ da la
poscondición. El costo sale de que cada vuelta descarta la mitad de la
ventana, lo que da la recurrencia T(N) = T(N/2) + Θ(1). ∎
Compare este código con el de la clase: son el mismo, línea por línea.
Lo único que cambió fue la condición de la línea 6, es decir el
predicado. Ese es el trabajo de verdad en un problema nuevo.
7. El error de siempre
La línea 8 dice r = mitad, no
r = mitad - 1. Cambie mentalmente esa línea y corra
[0, 1, 2, 3, 4]: en algún chequeo la posición del mínimo queda por fuera
de la ventana y el invariante se rompe, aunque el programa siga
entregando un número.
La razón está en el rango medio abierto: mitad ya se probó
y cumple el predicado, así que sigue siendo candidata a ser el
borde. Descartarla es descartar la respuesta. En la otra rama sí se puede
escribir mitad + 1, porque ahí mitad no lo
cumple.
8. Para llevarse
Sin solución aquí. Dos preguntas.
Primera: con la posición del mínimo ya calculada, escriba una función
que decida si un valor v está en el arreglo rotado, en Θ(lg N). ¿Cuál es
ahora el predicado, y sobre qué tramo se busca?
Segunda: si el arreglo puede tener elementos repetidos —por ejemplo
[2, 2, 2, 1, 2]—, ¿sigue siendo monótono p(t): A[t] ≤ A[N−1]? Encuentre
el chequeo donde la búsqueda toma la decisión equivocada, y diga cuánto
cuesta el peor caso cuando la monotonía se pierde.