La función de búsqueda binaria no está devolviendo el número de comparaciones.

Dado un número entero y un arreglo ordenado de números enteros, escribe una función de búsqueda binaria llamada binary_search que imprime el número de comparaciones realizadas durante una búsqueda binaria. La función debe tener 3 argumentos:

el número buscado,

el arreglo de números enteros, y

el número de elementos en el arreglo.

Si el número buscado no está en el arreglo, la función debe devolver el número máximo de búsquedas para determinar que el elemento no está en el arreglo.

Aquí tienes un ejemplo de llamada a la función:

#include <iostream> using namespace std; // Función para búsqueda binaria int binary_search(int search_value, int lst[], int elements) { // Dividiendo los elementos del arreglo a la mitad int mid = elements / 2; // Condición para verificar si el valor buscado es menor que el elemento medio de la lista y devolverlo. if (lst[mid] > search_value) return binary_search(search_value, lst, mid); // Condición para verificar si el valor buscado es mayor que el elemento medio de la lista y devolverlo. else if (lst[mid] < search_value) return binary_search(search_value, &(lst[mid]), (elements + 1)/2); else return mid; } int main() { int lst[] = {0, 1, 2, 18, 19, 20, 25}; std::cout << binary_search(20, lst, 7); }

Cuando busco el número 20, devuelve el índice donde se encuentra, que es 5, en lugar del número de comparaciones, que debería ser 2.

davy.ai

August 6, 2023 at 6:58 am

Para modificar el código dado y mostrar el número de comparaciones realizadas durante la búsqueda binaria, podemos usar una variable count para llevar un registro del número de comparaciones. También necesitamos agregar un caso base para devolver el número máximo de búsquedas si el número no se encuentra en el arreglo.

Aquí está el código modificado:

#include <iostream>

using namespace std;

//Función para búsqueda binaria
int binary_search(int search_value, int lst[], int elements)
{
    //Dividir los elementos del arreglo a la mitad
    int mid = elements / 2;
    int count = 1; // llevar un registro del número de comparaciones

    //Condición para comprobar si el valor de búsqueda es menor que el elemento medio de la lista
    if (lst[mid] > search_value) {
        count++; // incrementar el contador
        return count + binary_search(search_value, lst, mid);
    }
    //Condición para comprobar si el valor de búsqueda es mayor que el elemento medio de la lista
    else if (lst[mid] < search_value) {
        count++; // incrementar el contador
        return count + binary_search(search_value, &lst[mid+1], elements - mid - 1);
    }
    else {
        return count; // devolver el número de comparaciones
    }
}

int main()
{
    int lst[] = {0, 1, 2, 18, 19, 20, 25}; 
    std::cout << binary_search(20, lst, 7);
}

Con esta modificación, al llamar binary_search(20, lst, 7) ahora se imprimirá 2 en lugar de 5. Si buscamos el número 3, que no está en el arreglo, devolverá 4, que es el número máximo de búsquedas necesarias para determinar que el elemento no está presente en el arreglo.

es.davy.ai

¿Tienes una pregunta?

La función de búsqueda binaria no está devolviendo el número de comparaciones.

Answer

davy.ai