Capítulo 5. Divide y Conquista (Parte I)

Características

La técnica de Divide y Conquista se basa en dividir un problema grande en problemas más pequeños, más simples de resolver, para luego combinar las soluciones y resolver el problema original.

Los subproblemas en los que se divide el problema original deben ser de igual naturaleza entre sí y de igual naturaleza al del problema original. También, estos subproblemas deben ser de menor tamaño que el problema original, de tamaños similares, e independientes entre sí.

Hay casos donde el problema original no se divide en varios subproblemas sino en un único subproblema. La división se realiza en forma recurrente hasta que el tamaño del subproblema sea lo suficientemente pequeño para ser resuelto en forma simple (lo que llamamos el caso base en capítulos anteriores).

Búsqueda Binaria

Veremos el ejemplo más simple y conocido que resuelve la técnica de Divide y Conquista. El problema consiste en indicar si un elemento dado 'x' se encuentra presente en una secuencia ordenada de números 'S' también dada.

La Búsqueda Binaria consiste en seleccionar el elemento que está en el medio de la secuencia S. Si este elemento coincide con el 'x' que se desea encontrar, entonces podemos afirmar que 'x' pertenece a la secuencia 'S'. Sino, ya que la secuencia está ordenada, realizaremos una comparación entre el elemento del medio que seleccionamos y el 'x'.

Tenemos dos posibilidades: el elemento del medio de la secuencia es mayor o menor al 'x' buscado (ya vimos que sucedía si era igual).

Ahora veremos cómo es que nuestro problema original se divide en un subproblema más pequeño. Si el elemento del medio de la secuencia 'S' es mayor al 'x' buscado, al estar la cadena 'S' ordenada, querrá decir que la única chance de encontrar a 'x' estará a la izquierda del elemento medio (la primera mitad de la secuencia 'S').

De esta forma, procederemos a aplicar la misma técnica (seleccionar el elemento medio) pero ahora nuestra nueva secuencia 'S' será la primera mitad de la cadena original.

Así, utilizando Divide y Conquista, hemos logrado reducir el problema original a un subproblema menor (tenemos sólo la mitad de la cadena) con las mismas características que el problema original.

De igual manera, si el elemento del medio de la cadena original 'S' hubiera sido menor al elemento buscado 'x', nos tendríamos que haber quedado con la segunda mitad de la cadena 'S'. Es importante enfatizar que esto es posible pura y exclusivamente si la cadena 'S' está ordenada de menor a mayor, sino no existe forma de saber con qué mitad quedarnos.

Presentamos entonces el pseudocódigo para el algoritmo de Búsqueda Binaria:

Fuentes:
Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.