Me pueden ayudar a hacer una Búsqueda Binaria Recursiva Dinamica

Iniciado por gibranini, 8 Julio 2014, 07:23 AM

0 Miembros y 2 Visitantes están viendo este tema.

gibranini

Hola amigos, me pudieran ayudar con esta busqueda binaria recursiva, estoy haciendo una lista dinamica;

int busqueda binaria(int A[],int X, int i, int j)
{
     int medio;
     if (i>j)
     {
         return 0;
     }
     medio = (i+j) / 2;

     if (A[medio] < X)
     {   
         return busqueda binaria(A,X,medio+1,j);
     }     
     
     else if (A[medio] > X)
     {
         return busqueda binaria(A,X,i,medio-1);
     }

     else
     {
         return medio;
      }
}


y esto es lo que llevo pero me marca errores y no tengo idea en que estoy mal,

int Lista::BusquedaBinariaRecursiva(Nodo *aux[], string buscar, int i, int j)
{
    int medio;

    i=0;
    j=contador;//Es un contador variable, lleva el registro del numero de datos ingresados

    if(i>j)
    {
        return 0;
    }

    medio=(i+j)/2;

    if(aux[medio] <buscar)
    {
        return BusquedaBinariaRecursiva(aux, buscar, medio+1, j);
    }
    else if(aux[medio] >buscar)
    {
        return BusquedaBinariaRecursiva(aux, buscar, i, medio-1);
    }
    else
    {
        return medio;
    }

}


:(

Gh057

hola gibranini , por favor fíjate en los errores de compilación; solo a simple vista se observa que no llamas a la misma función que tienes definida... saludos
4 d0nd3 1r4 3l gh057? l4 r3d 3s 74n v4s74 3 1nf1n1t4...

eferion

Cita de: Gh057 en  8 Julio 2014, 12:25 PM
hola gibranini , por favor fíjate en los errores de compilación; solo a simple vista se observa que no llamas a la misma función que tienes definida... saludos

A mi me da la sensación de que el segundo código intenta ser una versión del primero pero encapsulado en una clase...

gibranini... cuando has puesto:

Código (cpp) [Seleccionar]
j=contador;//Es un contador variable, lleva el registro del numero de datos ingresados

¿En qué estabas pensando?... si se supone que i y j son los límites de la búsqueda no viene a cuento modificar 'j' con un valor que te estás sacando de la manga.

Gh057

tienes razón eferion, me expresé mal, quise decir que si la primera fuera una función recursiva no se llamaría a si misma ya que el espacio haría tirar error de función no definida...

con respecto a la segunda, exacto; sería implementarla en una clase.

gibranini, con respecto a la búsqueda binaria primero debes entender el concepto; la misma se produce partiendo el arreglo o vector previamente ordenado en dos partes y comparando el valor a encontrar con nuestro punto de pivote; si es menor repite en el extremo inferior, si es mayor en el superior.

si quieres hacerla recursiva, debes llamarla nuevamente (mientras tu condición de escape no se cumpla, o sea que no encuentres el valor entre los extremos) disminuyendo el tamaño del arreglo y realizando la nueva comparación en el extremo que podría contener nuestro valor requerido.

es muy útil en arreglos y vectores muy grandes.saludos


4 d0nd3 1r4 3l gh057? l4 r3d 3s 74n v4s74 3 1nf1n1t4...