Búsqueda binaria en arreglos de cadena con C

Búsqueda binaria en arreglos de cadenas con C

2 comentarios / Algoritmos, Lenguaje de programación C / Por

Introducción

Esto es el complemento a la entrada publicada anteriormente sobre la búsqueda binaria en C sobre arreglos de números.

Ahí buscamos en arreglos de números, ahora nos toca buscar en arreglos de cadenas. Igualmente aplicaremos la forma recursiva y con el ciclo while.

Los arreglos de cadenas son una cosa un poco complicada al inicio, sobre todo en este lenguaje. Por eso te invito a que leas cómo trabajar con arreglos de cadenas en C.

Por cierto, para una explicación más detallada o si quieres ver este algoritmo en otros lenguajes, visita: algoritmo de búsqueda binaria en varios lenguajes de programación.

Búsqueda binaria en arreglos de cadena con C
Búsqueda binaria en arreglos de cadena con C

Explicación

Ya lo expliqué en el post anterior que está citado al inicio. Aquí sólo explicaremos las funciones y la forma de comparar; la cosa no cambia mucho.

En C, para comparar una cadena usamos la función strcmp que está en la librería estándar y también en string.h.

Esta función funciona como strcmp en PHP; devuelve -1, 0 o 1 dependiendo de la comparación de las cadenas. Si la primera es menor que la segunda, devuelve menos 1. Si son iguales, devuelve 0. Y si la primera es mayor que la segunda devuelve 1.

De esta manera usamos el resultado para comparar las cadenas  y saber si debemos ir a la izquierda o a la derecha.

Búsqueda binaria recursiva en arreglos de cadenas en C

Aquí la función:

/**
 * 
 * Implementación del algoritmo de 
 * búsqueda binaria recursiva en un arreglo usando C
 * 
 * Funciona con arreglos de cadenas
 * 
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */
int busquedaBinariaRecursiva(char arreglo[][MAXIMA_LONGITUD_CADENA], char busqueda[], int izquierda, int derecha){
    if (izquierda > derecha) return -1;
    int indiceDeLaMitad = floor((izquierda + derecha) / 2);
    char *elementoDeLaMitad = arreglo[indiceDeLaMitad];
 
    int resultadoDeLaComparacion = strcmp(busqueda, elementoDeLaMitad);
 
    // Si son iguales hemos encontrado el elemento
    if (resultadoDeLaComparacion == 0) return indiceDeLaMitad;
 
    // Si no, vemos en cuál mitad podría estar
 
    // ¿A la izquierda?
    if (resultadoDeLaComparacion < 0){
        derecha = indiceDeLaMitad - 1;
    }else{
        // A la derecha
        izquierda = indiceDeLaMitad + 1;
    }
    // Recursión justo aquí
    return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
}

Lo que cambia es que en lugar de comparar números, comparamos la cadena y luego comparamos su resultado.

Más abajo ejecutaremos una prueba, sigue leyendo si deseas verla.

Búsqueda binaria con el ciclo while en C sobre arreglos de cadenas

Lo mismo que arriba, pero usamos un ciclo while que se rompe si izquierda es mayor que derecha.

Si no entiendes de lo que hablo, lee los otros posts en donde se explica detalladamente.

/**
 * 
 * Implementación del algoritmo de 
 * búsqueda binaria con while en un arreglo usando C
 * 
 * Funciona con arreglos de cadenas
 * 
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */
int busquedaBinariaWhile(char arreglo[][MAXIMA_LONGITUD_CADENA], char busqueda[], int longitudDelArreglo){
    int izquierda = 0, derecha = longitudDelArreglo - 1;
    while(izquierda <= derecha){
        int indiceDeLaMitad = floor((izquierda + derecha) / 2);
        char *elementoDeLaMitad = arreglo[indiceDeLaMitad];
 
        int resultadoDeLaComparacion = strcmp(busqueda, elementoDeLaMitad);
        // Si son iguales hemos encontrado el elemento
        if (resultadoDeLaComparacion == 0) return indiceDeLaMitad;
 
        // Si no, vemos en cuál mitad podría estar
 
        // ¿A la izquierda?
        if (resultadoDeLaComparacion < 0){
            derecha = indiceDeLaMitad - 1;
        }else{
            // A la derecha
            izquierda = indiceDeLaMitad + 1;
        }
    }
    // Si termina el ciclo y no encontramos nada, regresamos -1
    return -1;
}

Recibe, aparte del arreglo y la búsqueda, la longitud del arreglo. Esto es porque no podemos calcular ese dato dentro de la función.

Cómo usar estas funciones de búsqueda binaria en cadenas

Ahora sí veamos cómo se pueden usar. Para ello declaramos un arreglo, una búsqueda, buscamos e imprimimos el resultado.

Todo el código quedaría así:

#include <stdio.h>// printf
#include <string.h>// strcmp
#include <math.h>// floor
#define MAXIMA_LONGITUD_CADENA 50

// Prototipo de las funciones
int busquedaBinariaRecursiva(char arreglo[][MAXIMA_LONGITUD_CADENA], char busqueda[], int izquierda, int derecha);
int busquedaBinariaWhile(char arreglo[][MAXIMA_LONGITUD_CADENA], char busqueda[], int longitudDelArreglo);

int main(){
    char arreglo[][MAXIMA_LONGITUD_CADENA] = {"Arsenal", "Bautizo", "Comadreja", "Consulta", "Dinosaurio", "Zapato"};
    char busqueda[] = {"Zapato"};
    int longitudDelArreglo = sizeof(arreglo) / sizeof(arreglo[0]);


    int resultadoRecursivo = busquedaBinariaRecursiva(arreglo, busqueda, 0, longitudDelArreglo - 1);
    printf("Con recursividad, %s se encuentra en %d\n", busqueda, resultadoRecursivo);


    int resultadoConWhile = busquedaBinariaWhile(arreglo, busqueda, longitudDelArreglo);
    printf("Con while, %s se encuentra en %d\n", busqueda, resultadoConWhile);
}


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

    int resultadoDeLaComparacion = strcmp(busqueda, elementoDeLaMitad);

    // Si son iguales hemos encontrado el elemento
    if (resultadoDeLaComparacion == 0) return indiceDeLaMitad;

    // Si no, vemos en cuál mitad podría estar

    // ¿A la izquierda?
    if (resultadoDeLaComparacion < 0){
        derecha = indiceDeLaMitad - 1;
    }else{
        // A la derecha
        izquierda = indiceDeLaMitad + 1;
    }
    // Recursión justo aquí
    return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
}


/**
 * 
 * Implementación del algoritmo de 
 * búsqueda binaria con while en un arreglo usando C
 * 
 * Funciona con arreglos de cadenas
 * 
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */
int busquedaBinariaWhile(char arreglo[][MAXIMA_LONGITUD_CADENA], char busqueda[], int longitudDelArreglo){
    int izquierda = 0, derecha = longitudDelArreglo - 1;
    while(izquierda <= derecha){
        int indiceDeLaMitad = floor((izquierda + derecha) / 2);
        char *elementoDeLaMitad = arreglo[indiceDeLaMitad];

        int resultadoDeLaComparacion = strcmp(busqueda, elementoDeLaMitad);
        // Si son iguales hemos encontrado el elemento
        if (resultadoDeLaComparacion == 0) return indiceDeLaMitad;

        // Si no, vemos en cuál mitad podría estar

        // ¿A la izquierda?
        if (resultadoDeLaComparacion < 0){
            derecha = indiceDeLaMitad - 1;
        }else{
            // A la derecha
            izquierda = indiceDeLaMitad + 1;
        }
    }
    // Si termina el ciclo y no encontramos nada, regresamos -1
    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.

2 comentarios en “Búsqueda binaria en arreglos de cadenas con C”

Dejar un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *