Python: divide y vencerás

En el enfoque de divide y vencerás, el problema en cuestión se divide en subproblemas más pequeños y luego cada problema se resuelve de forma independiente. Cuando seguimos dividiendo los subproblemas en subproblemas aún más pequeños, es posible que finalmente lleguemos a una etapa en la que no sea posible más división. Se resuelven esos subproblemas (fracciones) "atómicos" más pequeños posibles. La solución de todos los subproblemas se fusiona finalmente para obtener la solución de un problema original.

En general, podemos entender divide-and-conquer enfoque en un proceso de tres pasos.

Dividir / romper

Este paso implica dividir el problema en subproblemas más pequeños. Los subproblemas deben representar una parte del problema original. Este paso generalmente toma un enfoque recursivo para dividir el problema hasta que ningún subproblema sea más divisible. En esta etapa, los subproblemas se vuelven de naturaleza atómica pero aún representan una parte del problema real.

Conquistar / Resolver

Este paso recibe muchos subproblemas más pequeños que deben resolverse. Generalmente, en este nivel, los problemas se consideran "resueltos" por sí mismos.

Fusionar / Combinar

Cuando se resuelven los subproblemas más pequeños, esta etapa los combina recursivamente hasta que formulan una solución del problema original. Este enfoque algorítmico funciona de forma recursiva y los pasos de conquistar y fusionar funcionan tan cerca que parecen uno solo.

Ejemplos

El siguiente programa es un ejemplo de divide-and-conquer enfoque de programación donde la búsqueda binaria se implementa utilizando Python.

Implementación de búsqueda binaria

En la búsqueda binaria tomamos una lista ordenada de elementos y comenzamos a buscar un elemento en el medio de la lista. Si el valor de búsqueda coincide con el valor medio de la lista, completamos la búsqueda. De lo contrario, eliminamos la mitad de la lista de elementos eligiendo si continuar con la mitad derecha o izquierda de la lista según el valor del elemento buscado. Esto es posible porque la lista está ordenada y es mucho más rápida que la búsqueda lineal. Aquí dividimos la lista dada y conquistamos eligiendo la mitad adecuada de la lista. Repetimos este enfoque hasta encontrar el elemento o concluir sobre su ausencia en la lista.

def bsearch(list, val):

    list_size = len(list) - 1

    idx0 = 0
    idxn = list_size
# Find the middle most value

    while idx0 <= idxn:
        midval = (idx0 + idxn)// 2

        if list[midval] == val:
            return midval
# Compare the value the middle most value
        if val > list[midval]:
            idx0 = midval + 1
        else:
            idxn = midval - 1

    if idx0 > idxn:
        return None
# Initialize the sorted list
list = [2,7,19,34,53,72]

# Print the search result
print(bsearch(list,72))
print(bsearch(list,11))

Cuando se ejecuta el código anterior, produce el siguiente resultado:

5
None