Divide y vencerás

DYV

El método está basado en la resolución recursiva de un problema dividiéndolo en dos o más subproblemas de igual tipo o similar.

Búsqueda binaria

Buscar el número 18 en la siguiente lista ORDENADA de números:

​

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23]

public static int busquedaBinaria(int vector[], int dato){�

….

� }

​

public static int busquedaBinaria(int vector[], int dato){� int centro, inf = 0, sup = n - 1;

� }

​

public static int busquedaBinaria(int vector[], int dato){� int centro, inf = 0, sup = n - 1;

while(inf <= sup) {� � }

� }

​

public static int busquedaBinaria(int vector[], int dato){� int centro, inf = 0, sup = n - 1;

while(inf <= sup) {� centro = ( sup + inf ) / 2;� }

� }

​

public static int busquedaBinaria(int vector[], int dato){� int centro, inf = 0, sup = n - 1;

while(inf <= sup) {� centro = ( sup + inf ) / 2;

if(vector[centro] == dato) return centro;

​

� }

� }

​

public static int busquedaBinaria(int vector[], int dato){� int centro, inf = 0, sup = n - 1;

while(inf <= sup) {� centro = ( sup + inf ) / 2;

if(vector[centro] == dato) return centro;

else if(dato < vector [centro] ){� sup = centro - 1;� }

​

� }

� }

​

public static int busquedaBinaria(int vector[], int dato){� int centro, inf = 0, sup = n - 1;

while(inf <= sup) {� centro = ( sup + inf ) / 2;

if(vector[centro] == dato) return centro;

else if(dato < vector [centro] ){� sup = centro - 1;� } else {� inf = centro + 1;� }� }

� }

​

public static int busquedaBinaria(int vector[], int dato){� int centro, inf = 0, sup = n - 1;

while(inf <= sup) {� centro = ( sup + inf ) / 2;

if(vector[centro] == dato) return centro;

else if(dato < vector [centro] ){� sup = centro - 1;� } else {� inf = centro + 1;� }� }

return -1;� }

​

Divide y vencerás

Diseño e implementación

1. Descomponer el problema en K problemas de MENOR tamaño, pero del MISMO tipo.
2. Resolverse todos los subproblemas, tanto si son elementales, como si son compuestos.
3. Combinar las soluciones.

Mergesort

Ordenamiento por mezcla

inf = 0, sup = 7, med = 3

Exponenciación Binaria

Ejercicios

• Exact Sum
• Solve It
• Fill the Containers
• The Monkey and the Oiled Bamboo