bsearch în C

#include <stdlib.h>
void *bsearch(const void *cheie, const void *baza, size_t numar, size_t marime,
              int (*compara)(const void *, const void *));

Ce face bsearch

Căutarea binară compară cheia cu elementul din mijloc, apoi continuă doar în jumătatea potrivită. Pentru 1.000.000 de elemente sunt nevoie de cel mult aproximativ 20 de comparații. Condiția: tabloul trebuie să fie sortat după același criteriu ca funcția de comparare.

Funcția de comparare primește întâi pointerul la cheie, apoi pointerul la un element din tablou. De obicei folosești aceeași funcție ca la qsort.

Rezultatul este un pointer la elementul găsit; poziția este p - tablou. Dacă există mai multe elemente egale, nu se știe pe care îl găsește.

Parametri

Parametru	Descriere
cheie	Pointer la valoarea căutată.
baza, numar, marime	Tabloul sortat, ca la qsort.
compara	Funcția de comparare (cheie, element).

Ce returnează

Pointer la elementul găsit sau NULL.

Exemple

Exemplul 1: Este codul poștal în listă?

#include <stdio.h>
#include <stdlib.h>

static int compara_int(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return (x > y) - (x < y);
}

int main(void) {
    int coduri[] = {400001, 500003, 700115, 700259, 900178};  // sortate
    int cautate[] = {700259, 300011};
    for (size_t i = 0; i < 2; i++) {
        int *p = bsearch(&cautate[i], coduri, 5, sizeof coduri[0], compara_int);
        if (p != NULL) {
            printf("%d găsit la poziția %td\n", cautate[i], p - coduri);
        } else {
            printf("%d nu este în listă\n", cautate[i]);
        }
    }
    return 0;
}

Rezultat

700259 găsit la poziția 3
300011 nu este în listă

Exemplul 2: Căutare într-un tablou de structuri, după nume

Cheia este un șir, iar elementele sunt structuri; funcția de comparare tratează diferit cele două argumente.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct judet {
    const char *cod;
    const char *nume;
};

static int compara_cod(const void *cheie, const void *element) {
    const struct judet *j = element;
    return strcmp(cheie, j->cod);
}

int main(void) {
    const struct judet judete[] = {{"BV", "Brașov"}, {"CJ", "Cluj"}, {"IS", "Iași"}, {"TM", "Timiș"}};
    const struct judet *j = bsearch("IS", judete, 4, sizeof judete[0], compara_cod);
    printf("IS = %s\n", j ? j->nume : "necunoscut");
    return 0;
}

Rezultat

IS = Iași

Greșeli frecvente

• Cauți într-un tablou nesortat: bsearch poate întoarce NULL chiar dacă elementul există.
• Tabloul este sortat crescător, iar funcția de comparare la căutare este descrescătoare (sau invers).

Comenzi înrudite

• qsort: Sortează un tablou de orice tip, folosind o funcție de comparare scrisă de tine.
• Pointeri la funcții: O variabilă care ține adresa unei funcții: o poți schimba, pune în tablouri sau trimite altor funcții (callback).
• void * (pointer generic): Un pointer care poate păstra adresa oricărui tip de date, dar care trebuie convertit la un tip concret înainte de folosire.
• strcmp și strncmp: Compară două șiruri caracter cu caracter și spune dacă sunt egale sau care vine primul.