← Volver a los ejercicios

rotado: inventar el predicado

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)mitadA[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.