Implementación y Funcionamiento de Búsqueda Binaria y Operaciones POP en Estructuras de Datos

1. El Algoritmo de Búsqueda Binaria

a) Implementación del Algoritmo de Búsqueda Binaria

A continuación, se presenta el pseudocódigo corregido para la Búsqueda Binaria, asumiendo que v es el vector donde se realiza la búsqueda y volumen es su tamaño.

int BusquedaBinaria(int buscado, int volumen, int v[]) {
    int der, izq, encontrado, medio;
    izq = 0;
    der = volumen - 1;
    encontrado = 0;

    while (izq <= der && encontrado == 0) {
        // Cálculo del punto medio (evitando desbordamiento de enteros)
        medio = izq + (der - izq) / 2; 

        if (v[medio] == buscado) {
            encontrado = 1;
        } else if (v[medio] > buscado) {
            // El valor buscado está en la mitad izquierda
            der = medio - 1;
        } else { // v[medio] < buscado
            // El valor buscado está en la mitad derecha
            izq = medio + 1;
        }
    }

    if (encontrado == 1) {
        printf("Valor encontrado en la posición %d\n", medio);
        return medio;
    } else {
        printf("No Encontrado\n");
        return -1;
    }
}

b) Descripción del Funcionamiento del Algoritmo

La Búsqueda Binaria es un algoritmo eficiente que utiliza el método de 'Divide y Vencerás' para localizar un valor deseado dentro de una lista o vector ordenado.

El funcionamiento se basa en los siguientes pasos:

1. Se examina el elemento central de la lista.
2. Si este elemento central es el valor buscado, la búsqueda finaliza exitosamente.
3. En caso contrario, se determina si el elemento buscado debe estar en la primera o la segunda mitad de la lista, basándose en si el valor buscado es menor o mayor que el elemento central.
4. Se descarta la mitad de la lista que no contiene el valor.
5. Este proceso se repite iterativamente (utilizando el elemento central de la sublista restante) hasta que se encuentra el valor o hasta que el subconjunto de búsqueda queda vacío.

c) Características y Requisitos para la Ejecución

Para que el algoritmo de Búsqueda Binaria pueda ejecutarse de manera correcta y eficiente, deben cumplirse las siguientes características:

• Ordenamiento de Datos: Los datos del vector deben estar previamente ordenados (ya sea de forma ascendente o descendente).
• Estructura de Datos: Los datos deben estar contenidos en una estructura que permita el acceso directo o aleatorio, típicamente un vector o array.
• Conocimiento del Volumen: Debe conocerse el número total de registros o el tamaño del vector para establecer los límites iniciales (izquierda y derecha).
• Acceso Aleatorio: La estructura debe permitir acceder a cualquier elemento en tiempo constante $O(1)$ (requisito inherente al uso de vectores).

d) Trazabilidad del Algoritmo

Realice una traza de un arreglo de 10 elementos de tipo entero con valores supuestos por usted, detallando los cambios en las variables izq, der y medio en cada iteración.

2. Desarrollo y Comparación de Algoritmos POP (Cola y Pila)

A continuación, se desarrollan y comparan los algoritmos de la operación POP (extracción de un elemento) para las estructuras de datos Cola (FIFO) y Pila (LIFO).

Aunque la lógica general de liberación de memoria es similar, la diferencia fundamental radica en cómo se gestionan los punteros de inicio y fin, especialmente en la Cola.

Prácticamente todo el algoritmo es idéntico. La única diferencia es que en el algoritmo de Cola, si el primer nodo resulta ser nulo después de la extracción, haremos que el puntero último también apunte a nulo, ya que la cola habrá quedado vacía.

Pasos para la Operación POP (Desencolar) en una Cola

El proceso de extracción (POP o Dequeue) de un elemento en una cola se realiza siguiendo la política FIFO (First In, First Out) y consta de los siguientes pasos:

1. Hacemos que un nodo temporal apunte al primer elemento de la cola, es decir, a primero.
2. Asignamos a primero la dirección del segundo nodo de la cola: primero->siguiente.
3. Guardamos el contenido del nodo temporal para devolverlo como retorno.
4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
5. Control de Vacío: Si primero es NULL (la cola ha quedado vacía), haremos que último también apunte a NULL.

3. Implementación de Búsqueda en una Cola mediante Lista Enlazada

Utilizando una lista lineal enlazada, implemente una búsqueda sobre una estructura de datos tipo cola.