Introducción a Binary Search y Recursividad

Escrito por intentodeobjetividad 03-06-2016 en General. Comentarios (0)

La recursividad consiste en resolver problemas reduciéndolos en tamaño pero manteniendo su esencia. Por otro lado, binary search permite buscar valores en un conjuntos de números de forma optima. Combinando estos dos conceptos podemos resolver un problema interesante que estuvo presente en la final de la conocida competencia interuniversitaria de programación organizada por ACM.

Básicamente tenemos un cubo de queso de 100x100x100 milímetros que contiene agujeros. Nuestro objetivo es cortar el queso en partes de igual peso sabiendo que un agujero lo reduce. Los datos que nos dan son la cantidad de partes y la cantidad, posición y tamaño de los agujeros. Lo que necesitamos calcular es en qué posiciones del eje Z hay que cortarlo. En principio, es fácil saber el peso total del cubo y en consecuencia, el peso que debe tener cada parte. Por ejemplo, si tenemos un solo agujero en (10,20,10) y de radio 10:

Peso Total = 100*100*100 - 4*pi*(radio^3) / 3 = 100*100*100 - 4*pi*(10^3) / 3 = 1000000 - 4188.8 = 995811.2

Si queremos cortarlo en 5 partes:

Peso individual = 995811.2 / 5 = 199162.24

La parte más complicada es saber dónde hay que cortar el eje Z y cómo hacer que sea optimo ese análisis. Acá aparece el algoritmo de binary search que permite encontrar un valor en un conjunto ordenado de números. En primer lugar, compara con el elemento que se encuentra en el medio del array si es igual al valor buscado, ya lo encontramos, si no lo es, se genera un nuevo array. En el nuevo hacemos lo mismo que en el anterior y recursivamente resolvemos este problema. El array se reduce hasta que llegue a un solo elemento si es que antes no encontré el valor que buscaba. Por ejemplo:

[1, 2, 3, 7 , 9, 11, 13, 20, 100]

Valor 13:

9 < 13 => [11,13,20,100]

13 = 13 => Encontrado

Valor 1:

9 > 1 => [1,2,3,7]

2 > 1 => [1]

1 == 1 => Encontrado

Valor 4:

9 > 4 => [1,2,3,7]

2 < 4 => [3,7]

3 < 4 => [7]

7 != 4 :=> No encontrado

Claramente vemos cómo un problema mayor se traduce en problemas menores que en esencia son similares. La única diferencia entre cada etapa del procedimiento recursivo, es el tamaño del array pero el proceso es igual. Se compara con el valor que está en el medio, se separa el array en dos y se elige uno para continuar.

Esto no parece tan útil en arrays que contienen pocos elementos pero cuando la longitud crece, vemos que el binary search es mucho más rápido que una recorrida secuencial. El tiempo que tarda el primero crece logaritmicamente con la cantidad de números mientras el otro lo hace linealmente.

Si pensamos en el binary search de forma más general, podemos ver que los números reales son un conjunto infinito de elementos ordenados. Es un gran array que podemos recorrer. Nuestro algoritmo recibirá 3 variables como entrada. Un inicio y un fin que delimitan un intervalo de búsqueda y un valor que es el peso que quiero tener. La salida es el punto del eje Z donde debo cortar el queso para obtener el peso deseado.

1 - Calculo el valor medio del intervalo = (fin-inicio)/2.

2 - Calculo que peso posee este valor medio, si mi peso deseado es mayor, creo un nuevo intervalo [medio, fin], si mi peso es menor creo [inicio, medio]. De esta forma el intervalo se achica en cada iteracion.

3 - Con el nuevo intervalo repito el punto 1 y 2.

4 - Finalmente cuando estoy lo suficientemente cerca de mi peso objetivo, ya sé el Z que logra eso.

Con esta función ya hecha, el resto del problema planteado es trivial.