Ayuda entender Divide y Venceras

[fla2727]

Buenas, nos han explicado en programacion (en C) la tecnica divide y venceras, pero no me ha quedado claro como se haria este ejemplo, a la hora de combinar soluciones. A ver si alguien podría explicarmelo.

Ejemplo: Un algoritmo que busque la posición de un elemento, p, entre dos posiciones i,j de un vector, v, no ordenado. En caso de que exista devolverá la posición del elemento, en caso contrario devolverá -1. Para resolver el problema mediante recursividad, considere en dividir el problema en dos partes del mismo tamaño.

Mi solucion propuesta:

int encuentraPosicion2(int v[], int p, int i, int j){
   int r = -1;
   int m = (i+j)/2;
   if(i==j && p==v){
      r=i;
   }else if(p==v[m]){
      r=m;
   }else{
      r=encuentraPosicion2(v, p, i, m);
      r=encuentraPosicion2(v, p, m, j);
   }
   return r;
}

Pero se ve que no, que no entendí bien la idea....Alguien que sepa ayudarme

[fla2727]

Nadie?...

[m0rf]

Es una busqueda binaria?

[fla2727]

No creo que sea busqueda binaria porque no está ordenado el array. Seguí pensando y se me ocurrio lo siguiente:

Código [Seleccionar] Expandir


int max(int a, int b){
return (a>b)? a:b;
}


int encuentraPosicion2(int v[], int p, int i, int j){
int result = -1;
int m = (i+j)/2;
if(i==j && p==v[ i ]){
result=i;
}else if(p==v[m]){
result=m;
}else{
result=max(encuentraPosicion2(v, p, i, m),encuentraPosicion2(v, p, m, j));
}
return result;
}

pero sigue sin funcionar, alguna ayuda??

[m0rf]

Se más especifico la próxima vez, no me voy a poner a preguntar para ayudarte.

"Posteo un codigo, arreglamelo!"

[fla2727]

Ya está solucionado. Gracias por participar