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 idea en una frase
Partir en mitades, resolver cada una, y unir. Partir en mitades es lo que convierte n en log n.
Antes de ver codigo
Buscar una palabra en un diccionario de papel. Nadie empieza por la A: abres por la mitad, miras si tu palabra va antes o despues, y descartas media guia de un solo golpe. Repites. En unas veinte aperturas encuentras cualquier palabra de un diccionario de un millon de entradas.
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
Aqui es donde la teoria de arriba se vuelve concreta. Cambia los parametros, dale a Reproducir, y sobre todo usa las flechas para ir paso a paso: la velocidad automatica sirve para ver la forma general, pero lo que de verdad ensena es detenerse en un retorno y entender por que vuelve ahi y no a otro lado.
Errores que vas a cometer
No son ejemplos inventados: son los que aparecen una y otra vez en los parciales. Lee el codigo, decide tu mismo que esta mal, y solo despues abre la correccion. Si la abres de una, no aprendes nada.
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
Responde sin devolverte a leer. Si fallas no pasa nada: la explicacion te dice exactamente donde estaba el hueco, y ese es el momento en que de verdad se aprende. Con el 70% el nivel queda aprobado.