Lenguaje de programación C

Programa en C: búsqueda binaria recursiva y secuencial en arreglos

Introducción

Luego de algún tiempo he terminado de implementar la función recursiva y con ciclos para ejecutar el algoritmo de búsqueda binaria en un arreglo numérico en C.

Este algoritmo también es conocido como divide y vencerás; pues va dividiendo el arreglo en 2 hasta encontrar lo que buscamos, aunque como requisito dicho arreglo debe estar ordenado.

Explicación del algoritmo

Toma el elemento del medio del arreglo usando la función floor para redondear, lo compara con lo que buscamos y si coincide entonces regresa el índice.

En caso de que no, compara si lo que buscamos está a la izquierda o derecha del medio, y a partir de ello parte el arreglo desde la izquierda hasta la mitad, o desde la mitad hasta la derecha y así hasta terminar.

Para una más detallada, visita esta página en donde además podrás ver otras implementaciones en otros lenguajes.

Búsqueda binaria en C con recursión

La primera función que veremos es la que aplica recursión o recursividad:

/**
 * 
 * Implementación del algoritmo de 
 * búsqueda binaria recursiva en un arreglo usando C
 * 
 * Funciona con arreglos de números
 * 
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */int busquedaBinariaRecursiva(int arreglo[], int busqueda, int izquierda, int derecha){
    if (izquierda > derecha) return -1;
 
    int indiceDeLaMitad = floor((izquierda + derecha) / 2);
 
    int valorQueEstaEnElMedio = arreglo[indiceDeLaMitad];
    if (busqueda == valorQueEstaEnElMedio){
        return indiceDeLaMitad;
    }
    
    if (busqueda < valorQueEstaEnElMedio){
        // Entonces está hacia la izquierda
        derecha = indiceDeLaMitad - 1;
    }else{
        // Está hacia la derecha
        izquierda = indiceDeLaMitad + 1;
    }
    return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
}

La condición de salida varía: la primera es que se encuentre el elemento, ahí se regresa el índice en donde se encuentra lo que buscamos.

La segunda es cuando ya dividimos tantas veces y no encontramos nada, así que regresamos -1.

Para probar este algoritmo sigue bajando, dejaré todo eso hasta abajo.

Búsqueda binaria en C con ciclo while

Nota sobre la longitud del arreglo: en otros lenguajes, podríamos saber la longitud del arreglo que nos pasan. En C no es así porque cuando pasamos un arreglo como parámetro a una función, se convierte en puntero.

Podemos calcularla en el ámbito en donde se declara, esto es justo cuando llamamos a la función. Igual más abajo veremos cómo se hace; mientras tanto así es la función:

/**
 * 
 * Implementación del algoritmo de 
 * búsqueda binaria recursiva en un arreglo usando C
 * 
 * Funciona con arreglos de números
 * 
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */int busquedaBinariaConWhile(int arreglo[], int busqueda, int tamanioDelArreglo){
    // Nota: el tamaño del arreglo es necesario porque cuando se recibe
    // como argumento no se puede calcular dentro de la función
    int izquierda = 0, derecha = tamanioDelArreglo - 1;
    while (izquierda <= derecha){
        int indiceDeLaMitad = floor((izquierda + derecha) / 2);
 
        int valorQueEstaEnElMedio = arreglo[indiceDeLaMitad];
 
        if (busqueda == valorQueEstaEnElMedio){
            // En caso de encontrar lo que buscamos, terminamos la función
            // y regresamos el índice
            return indiceDeLaMitad;
        }
        
        if (busqueda < valorQueEstaEnElMedio){
            // Entonces está hacia la izquierda
            derecha = indiceDeLaMitad - 1;
        }else{
            // Está hacia la derecha
            izquierda = indiceDeLaMitad + 1;
        }
    }
    // Termina el ciclo y no encontramos nada
    return -1;
}

Es lo mismo, pues vamos cambiando los valores de derecha e izquierda; partiendo así el arreglo. En caso de encontrar lo que buscamos se regresa el índice; y si no (esto es cuando el ciclo termina) entonces -1.

Implementación de búsqueda binaria en C

Con este código podemos probar todo lo explicado arriba:

#include <stdio.h> // Para printf
#include <math.h> // Para floor

// Prototipos de las funciones
int busquedaBinariaRecursiva(int arreglo[], int busqueda, int izquierda, int derecha);
int busquedaBinariaConWhile(int arreglo[], int busqueda, int tamanioDelArreglo);

int main(){
    int numeros[] = {1, 2, 4, 8, 15, 16, 20, 50};
    int busqueda = 16;
    int longitudDelArreglo = sizeof(numeros) / sizeof(numeros[0]);
    int resultadoBusquedaRecursiva = busquedaBinariaRecursiva(numeros, busqueda, 0, longitudDelArreglo - 1);
    printf("Al buscar %d recursivamente, el resultado es %d\n", busqueda, resultadoBusquedaRecursiva);
    int resultadoBusquedaWhile = busquedaBinariaConWhile(numeros, busqueda, longitudDelArreglo);
    printf("Al buscar %d con while, el resultado es %d\n", busqueda, resultadoBusquedaWhile);
}

/**
 * 
 * Implementación del algoritmo de 
 * búsqueda binaria recursiva en un arreglo usando C
 * 
 * Funciona con arreglos de números
 * 
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */int busquedaBinariaRecursiva(int arreglo[], int busqueda, int izquierda, int derecha){
    if (izquierda > derecha) return -1;

    int indiceDeLaMitad = floor((izquierda + derecha) / 2);

    int valorQueEstaEnElMedio = arreglo[indiceDeLaMitad];
    if (busqueda == valorQueEstaEnElMedio){
        return indiceDeLaMitad;
    }
    
    if (busqueda < valorQueEstaEnElMedio){
        // Entonces está hacia la izquierda
        derecha = indiceDeLaMitad - 1;
    }else{
        // Está hacia la derecha
        izquierda = indiceDeLaMitad + 1;
    }
    return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
}

/**
 * 
 * Implementación del algoritmo de 
 * búsqueda binaria recursiva en un arreglo usando C
 * 
 * Funciona con arreglos de números
 * 
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */int busquedaBinariaConWhile(int arreglo[], int busqueda, int tamanioDelArreglo){
    // Nota: el tamaño del arreglo es necesario porque cuando se recibe
    // como argumento no se puede calcular dentro de la función
    int izquierda = 0, derecha = tamanioDelArreglo - 1;
    while (izquierda <= derecha){
        int indiceDeLaMitad = floor((izquierda + derecha) / 2);

        int valorQueEstaEnElMedio = arreglo[indiceDeLaMitad];

        if (busqueda == valorQueEstaEnElMedio){
            // En caso de encontrar lo que buscamos, terminamos la función
            // y regresamos el índice
            return indiceDeLaMitad;
        }
        
        if (busqueda < valorQueEstaEnElMedio){
            // Entonces está hacia la izquierda
            derecha = indiceDeLaMitad - 1;
        }else{
            // Está hacia la derecha
            izquierda = indiceDeLaMitad + 1;
        }
    }
    // Termina el ciclo y no encontramos nada
    return -1;
}

Estoy aquí para ayudarte 🤝💻


Estoy aquí para ayudarte en todo lo que necesites. Si requieres alguna modificación en lo presentado en este post, deseas asistencia con tu tarea, proyecto o precisas desarrollar un software a medida, no dudes en contactarme. Estoy comprometido a brindarte el apoyo necesario para que logres tus objetivos. Mi correo es parzibyte(arroba)gmail.com, estoy como@parzibyte en Telegram o en mi página de contacto

No te pierdas ninguno de mis posts 🚀🔔

Suscríbete a mi canal de Telegram para recibir una notificación cuando escriba un nuevo tutorial de programación.
parzibyte

Programador freelancer listo para trabajar contigo. Aplicaciones web, móviles y de escritorio. PHP, Java, Go, Python, JavaScript, Kotlin y más :) https://parzibyte.me/blog/software-creado-por-parzibyte/

Ver comentarios

Entradas recientes

Creador de credenciales web – Aplicación gratuita

Hoy te voy a presentar un creador de credenciales que acabo de programar y que…

2 días hace

Desplegar PWA creada con Vue 3, Vite y SQLite3 en Apache

Ya te enseñé cómo convertir una aplicación web de Vue 3 en una PWA. Al…

1 semana hace

Arquitectura para wasm con Go, Vue 3, Pinia y Vite

En este artículo voy a documentar la arquitectura que yo utilizo al trabajar con WebAssembly…

1 semana hace

Vue 3 y Vite: crear PWA (Progressive Web App)

En un artículo anterior te enseñé a crear un PWA. Al final, cualquier aplicación que…

1 semana hace

Errores de Comlink y algunas soluciones

Al usar Comlink para trabajar con los workers usando JavaScript me han aparecido algunos errores…

1 semana hace

Esperar promesa para inicializar Store de Pinia con Vue 3

En este artículo te voy a enseñar cómo usar un "top level await" esperando a…

1 semana hace

Esta web usa cookies.