Cómo funciona divide y vencerás

Partir por la mitad

Antes dijimos que una tarea grande se divide en pasos pequeños. Aquí vamos un paso más allá.
Partimos el problema por la mitad, cada mitad otra vez por la mitad, y así sucesivamente.
Los trozos se van haciendo cada vez más pequeños.

Cada pulsación parte todos los trozos por la mitad, y los trozos se van haciendo más pequeños.

Cada corte reduce a la mitad lo que hay que manejar.
La montaña grande abrumaba, pero un trozo pequeño es mucho más llevadero.
Es la misma sensación que buscar en un diccionario por mitades.

Los trozos no se superponen

Aquí hay algo muy importante: las dos mitades no se superponen.
El montón de la izquierda y el de la derecha no comparten ninguna prenda, así que lo que se hace en un lado no hay que repetirlo en el otro.
Las dos partes son completamente independientes.

Ilumina los dos trozos uno por uno: no hay ninguna parte en común. Como están separados (son independientes), resolver cada uno por su cuenta no causa choques.

Esta propiedad de no superponerse importa más de lo que parece.
Como los trozos no se superponen, la respuesta de un lado no estropea la del otro.
Cuando los trozos sí se superponen, la historia cambia, y eso lleva por otro camino.

Resolver los trozos pequeños

Si sigues partiendo, llegas a trozos diminutos que ya no se pueden partir.
Una prenda, un número.
Con ese tamaño se resuelven al instante, sin nada que pensar.

Toca los trozos más pequeños (el fondo) uno por uno para resolverlos al momento. Son tan pequeños que se resuelven sin esfuerzo y se vuelven verdes.

No nos esforzamos en resolver el problema grande de una sola vez.
Partimos hasta el fondo y luego resolvemos solo los trozos pequeños y fáciles, uno por uno.
Hemos convertido un trabajo difícil en muchos trabajos fáciles.

Juntar hacia arriba

Ahora que tenemos respuestas pequeñas, subimos de vuelta.
Juntamos dos respuestas pequeñas en una un poco mayor, y luego juntamos esas en otra aún mayor.
Tras juntar tantas veces como partimos, la respuesta completa queda arriba del todo.

Cada pulsación junta los trozos resueltos de dos en dos. Arriba del todo, la respuesta completa queda lista.

Al partir se baja; al juntar se sube.
Como los trozos no se superponían, juntar también es limpio: basta con reunir la respuesta de la izquierda y la de la derecha.
Esto es «divide y vencerás».

Partir, resolver, juntar

En una línea: partir por la mitad, resolver por separado los trozos que no se superponen y volver a juntarlos hacia arriba.
Ordenar cartas partiéndolas por la mitad sigue este esquema al pie de la letra, y buscar en un diccionario por mitades es el caso en que se descarta el lado sin el valor buscado, así que basta con resolver una mitad.
Lo grande se vuelve pequeño cuando se parte.

Toca los tres pasos en orden para dar una vuelta completa: partir por la mitad → resolver trozos pequeños → juntar hacia arriba. La clave es que los trozos no se superponen.

Aquí los trozos estaban bien separados, así que ninguno tuvo que resolverse dos veces.
Pero ¿y si los trozos se superpusieran y hubiera que resolver lo mismo una y otra vez?
En la próxima lección veremos primero la recursión, donde el partir se repite a sí mismo, y justo después llegaremos a esa bifurcación.