Calcular el punto medio con una suma
int medio = (ini + fin) / 2;
Con ini y fin grandes, la suma desborda el rango del int y el resultado se vuelve negativo. Excepcion al indexar.
int medio = ini + (fin - ini) / 2;
Divide y venceras
Partir en mitades, resolver, y unir.
La estrategia
Divide y venceras es un patron con tres tiempos exactos:
Dividir: partir el problema en subproblemas del mismo tipo, normalmente en mitades. Vencer: resolver cada mitad recursivamente. Combinar: unir las soluciones parciales en la solucion final.
La diferencia con la recursion multiple del nivel 3 es que aqui las partes no se solapan. Fibonacci recalcula lo mismo mil veces; mergesort ordena cada elemento exactamente una vez por nivel.
Busqueda binaria
El caso mas simple: divides, y descartas una mitad entera. No hay nada que combinar. Buscar en un arreglo ordenado de un millon de elementos cuesta 20 comparaciones.
static int buscar(int[] a, int obj, int ini, int fin) {
if (ini > fin) return -1; // caso base: no esta
int medio = ini + (fin - ini) / 2; // evita desbordamiento
if (a[medio] == obj) return medio;
if (a[medio] > obj) return buscar(a, obj, ini, medio - 1);
return buscar(a, obj, medio + 1, fin);
}
Escribir (ini + fin) / 2 es un bug real que estuvo 9 anos en la libreria estandar de Java. Con arreglos grandes, esa suma desborda el int.
Mergesort
Aqui si hay que combinar, y el combinar es donde esta todo el trabajo. Divides el arreglo en dos mitades, ordenas cada una recursivamente, y luego mezclas dos arreglos ya ordenados en uno solo.
El arbol tiene log n niveles y en cada nivel se toca cada elemento una vez: n log n. Y a diferencia de quicksort, ese n log n esta garantizado incluso en el peor caso.
static void mergeSort(int[] a, int ini, int fin) {
if (ini >= fin) return; // 0 o 1 elemento: ya ordenado
int medio = ini + (fin - ini) / 2;
mergeSort(a, ini, medio); // vencer izquierda
mergeSort(a, medio + 1, fin); // vencer derecha
mezclar(a, ini, medio, fin); // combinar
}
El teorema maestro, sin formalismos
Si un algoritmo hace a llamadas sobre problemas de tamano n/b y ademas gasta f(n) en dividir y combinar, el costo total depende de quien gana: el trabajo de las hojas o el trabajo de la combinacion.
Busqueda binaria: 1 llamada, mitad, combinar constante, da log n. Mergesort: 2 llamadas, mitad, combinar lineal, da n log n. Fibonacci ingenuo: 2 llamadas pero sobre n-1 y n-2, no sobre n/2, y por eso es exponencial. La division real en mitades es lo que produce el logaritmo.
Ejecuta y observa
Cambia los parametros, dale a Reproducir, y usa las flechas para avanzar paso a paso. La pila crece hacia arriba: el marco de arriba es el que se esta ejecutando ahora mismo.
Errores que vas a cometer
Lee el codigo, decide que esta mal, y despues abre la correccion.
Caso base mal puesto en mergesort
if (ini == fin) return;
Si por algun camino ini queda mayor que fin, la condicion no se cumple y la recursion sigue con rangos invalidos.
if (ini >= fin) return;
Comprueba lo que entendiste
Necesitas el 70% para dar el nivel por visto. Responde sin devolverte a la teoria: si fallas, la explicacion te dice exactamente donde estaba el hueco.