0

¿Es posible hacer una búsqueda binaria con listas ligadas?

Ya tengo el código para hacer una búsqueda binaria (tanto recursiva como iterativa), pero es para buscar un numero dentro de un arreglo. ¿Cómo puedo adaptarlo para buscar una posición en una lista ligada?

Por ejemplo: "Quiero buscar el Producto: 1"

Para así poder acceder a los datos en dicha posición.

Aquí esta la estructura:

struct Producto {
    wchar_t nombre[256];
    wchar_t cant[256];
    wchar_t imagen[200];
    wchar_t cod_barras[256];
    wchar_t marca[256];
    wchar_t descrip[256];
    wchar_t monto[256];
    Producto* siguiente;
    Producto* anterior;
};

Y este es el código para la búsqueda binaria para un arreglo:

void busqueda_binaria_recursiva(int mitad, int valor_a_buscar) 
{
    if (arreglo[mitad] == valor_a_buscar)
    {
        cout << "encontramos el numero" << endl;
    }
    else
    {
        if (valor_a_buscar > arreglo[mitad])
        {
            mitad = mitad + (mitad / 2);
            busqueda_binaria_recursiva(mitad, valor_a_buscar);
        }
        else
        {
            mitad = mitad / 2;
            busqueda_binaria_recursiva(mitad, valor_a_buscar);
        }
    }
}

void busqueda_binaria_iterativa(int mitad, int valor_a_buscar)
{
    bool condicion = true;
    for (int i = 0; condicion; i++)
    {
        if (arreglo[mitad] == valor_a_buscar)
        {
            cout << "encontramos el numero" << endl;
            condicion = false;
        }
        else
        {
            if (valor_a_buscar > arreglo[mitad])
            {
                mitad = mitad + (mitad / 2);
            }
            else
            {
                mitad = mitad / 2;
            }
        }
    }
}

1 respuesta 1

0

El concepto de búsqueda binaria lo tienes implementado, pero en lugar de trabajar sobre índices de formaciones1 deberás trabajar sobre iteradores.

En tu caso puedes usar como iterador los punteros de tu estructura de datos y necesitarás una manera de saber la distancia entre dos iteradores, por ejemplo:

int distancia(Producto *a, Producto *b)
{
    int resultado = 0;
    for (; a && a != b; a = a->siguiente)
        ++resultado;

    if (a)
        return resultado;

    return -1;
}

La función anterior avanza el puntero mientras el puntero tenga valor y sea diferente al puntero de destino; si no se encuentra el puntero buscado devuelve -1.

Otra operación que necesitarás será avanzar un iterador hasta un punto, por ejemplo:

void avanza(Producto *&p, int cantidad)
{
    for (; p && cantidad; --cantidad)
        p = p->siguiente;
}

La función anterior avanza el puntero cantidad veces.

Con esas funciones implementadas tu función de búsqueda recursiva podría parecerse a:

void busqueda_binaria_recursiva(Producto *a, Producto *b, int valor_a_buscar) 
{
    if (a->valor == valor_a_buscar)
    {
        std::cout << "encontramos el numero\n";
    }
    else
    {
        if (int punto_medio = distancia(a, b) / 2)
        {
            Producto *mitad = a;
            avanza(mitad, punto_medio);

            if (valor_a_buscar > mitad->valor)
            {
                busqueda_binaria_recursiva(mitad, b, valor_a_buscar);
            }
            else
            {
                busqueda_binaria_recursiva(a, mitad, valor_a_buscar);
            }
        }
        else
            busqueda_binaria_recursiva(b, b, valor_a_buscar);
    }
}

Puedes ver el código funcionando en Try it online!.


1También conocidas como arreglos o en ingles arrays.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.