Problema 3 · Programació II UDL 2010

a. Justificación conceptual del descarte de mitades en crossed(int[] asc, int[] desc, int left, int right)

Solución: Definimos la función de diferencia para cada índice $i$: $D(i) = asc[i] - desc[i]$. Dado que $asc$ es monótonamente creciente ($asc[i] \le asc[i+1]$) y $desc$ es monótonamente decreciente ($desc[i] \ge desc[i+1]$), la función $D(i)$ es monótona estrictamente no decreciente: si $i < j$, entonces $D(i) \le D(j)$. Buscamos si existe un índice donde $D(i) = 0$. En cada paso calculamos $mid = (left + right) / 2$: - Si $asc[mid] == desc[mid]$: se ha encontrado el índice, retornamos true. - Si $asc[mid] < desc[mid]$ ($D(mid) < 0$): para cualquier $i < mid$ se cumple $asc[i] \le asc[mid] < desc[mid] \le desc[i]$, por lo que nunca podrá cumplirse la igualdad; descartamos la mitad izquierda y buscamos recursivamente en la derecha ($mid + 1$, $right$). - Si $asc[mid] > desc[mid]$ ($D(mid) > 0$): para cualquier $i > mid$ se cumple $asc[i] \ge asc[mid] > desc[mid] \ge desc[i]$; descartamos la mitad derecha y buscamos en la izquierda ($left$, $mid - 1$). - Caso base de parada: si $left > right$, el intervalo se ha vaciado sin coincidencia, retornamos false.

a. Implementación en Java de la función recursiva crossed(int[] asc, int[] desc, int left, int right)

Solución: ```java if (left > right) { return false; } int mid = (left + right) / 2; if (asc[mid] == desc[mid]) { return true; } else if (asc[mid] < desc[mid]) { return crossed(asc, desc, mid + 1, right); } else { return crossed(asc, desc, left, mid - 1); } ```

b. Definir la invocación inicial desde crossed(int[] asc, int[] desc) para abarcar ambos vectores al completo.

Solución: ```java return crossed(asc, desc, 0, asc.length - 1); ```