Bsearch

ceer
void *bsearch (const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
<justify>Funkcja<font color="gray"> bsearch()</span> przeszukuje tablicę obiektów nmemb, której pierwszy element jest wskazywany przez wskaźnik base, w poszukiwaniu elementu pasującego do obiektu wskazywanego przez key. Rozmiar każdego z elementów tablicy określony jest przez size.</justify><justify> Zawartość tablicy powinna być posortowana w kolejności rosnącej zgodnie z funkcją porównawczą wskazywaną przez compar. Funkcja compar powinna posiadać dwa argumenty: wskaźnik do obiektu key oraz do elementu tablicy, i powinna zwracać wartość integer mniejszą, równą lub większą niż zero jeśli obiekt key okazał się, odpowiednio, mniejszy, równy lub większy niż element tablicy.</justify>

Parametry:<dl><dt>key</dt><dd>Szukany element.</dd><dt>base</dt><dd>Pierwszy element tablicy.</dd><dt>nmemb</dt><dd>Liczba elementów przeszukiwanej tablicy.</dd><dt>size</dt><dd>Rozmiar pojedynczego elementu w bajtach.</dd><dt>compar</dt><dd>Wskaźnik do funkcji porównującej elementy.</dd></dl>Zwracana wartość:
bsearch() zwraca wskaźnik do znalezionego elementu lub NULL gdy elementu nie znaleziono. Jeżeli tablica zawiera wiele elementów zgodnych ze wzorcem, nie jest określone który zostanie znaleziony.

Przykłady

#include <stdio.h>
#include <stdlib.h>
 
int compareIntegers (const void* a, const void* b)
{
        return (*(int*)a - *(int*)b);
}
 
int main (int argc, char* argv[])
{
        int* element;
        int szukana_wartosc = 25;
        int ciag[] = { 10, 20, 25, 40, 90, 100, 200, 400, 768, 769, 780, 781, 1000 };
 
        element = (int*) bsearch(&szukana_wartosc, ciag, 14, sizeof (int), compareIntegers);
        if ( element )
                printf ("%d znajduje sie w ciagu na pozycji %d.\n", *element, element-ciag+1);
        else
                printf ("%d nie znajduje sie w ciagu.\n", szukana_wartosc);
        return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main (int argc, char* argv[])
{
        char* element;
        char szukana_wartosc[20] = "sensu";
        char ciag[][20] = {"przykladowy","pozbawiony", "wiekszego", "sensu", "string"};
 
        qsort (ciag, 5, 20, (int(*)(const void*,const void*)) strcmp);        /* ← sortowanie elementów ciągu */
 
        element = (char*) bsearch_ (szukana_wartosc, ciag, 5, 20, (int(*)(const void*,const void*)) strcmp);
 
        if ( element )
                printf ("element '%s' znajduje sie w ciagu.\n", element);
        else
                printf ("element '%s' nie zostal znaleziony w ciagu.\n", szukana_wartosc);
        return 0;
}

Prosta implementacja

 /* ↓ what oznacza szukany element, low i high odpowiednio pierwszy i ostatni element przeszukiwanej tablicy */
int * binarySearch (int what, int *low, int *high)
{
        int *middle;        /* ← środkowy element tablicy */
        while ( high > low )
        {
                middle = low + (high - low) / 2;
                if ( *middle == what )
                        return middle;
                else if ( *middle > what )
                        high = middle;
                else
                        low = middle + 1;
        }
        return NULL;
}

Zobacz też:
qsort
Strcmp

0 komentarzy