Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Opracował: Piotr DejaVu Szawdyński
Język C++

bsearch

[funkcja] Wykonuje algorytm binarnego przeszukiwania na posortowanej tablicy.

Składnia

C/C++
#include <cstdlib>

void * bsearch(
const void * key,
const void * base,
size_t num,
size_t width,
int( * compare )( const void *, const void * )
);

Opis szczegółowy

Funkcja wykonuje algorytm binarnego przeszukiwania na posortowanej tablicy.

Argumenty

ArgumentOpis
const void *keyPoszukiwany klucz.
const void *baseWskaźnik na posortowaną tablicę, która ma zostać przeszukana.
size_t numLiczba elementów w tablicy.
size_t widthLiczba bajtów zajmowanych przez jeden element tablicy.
int (*compare ) ( const void *, const void *)Funkcja porównująca klucze. Do pierwszego argumentu przedmiotowej funkcji trafia wskaźnik na element poszukiwany key, natomiast do drugiego wskaźnik na element tablicy base z którym ma nastąpić porównanie.

Zwracana wartość

Funkcja zwraca wskaźnik na element tablicy (base), pasujący do szukanego klucza (key). Jeżeli klucz nie został znaleziony, funkcja zwraca wartość NULL. Jeżeli tablica nie jest posortowana rosnąco lub zawiera elementy posiadające zduplikowane klucze to wynik funkcji jest nieprzewidywalny.

Funkcja compare

Funkcja przekazana jako argument compare powinna zwracać następujące wartości:
  • mniejsze od 0 - gdy wartość argumentu pierwszego jest mniejsza od argumentu drugiego;
  • równe 0 - gdy wartość argumentu pierwszego jest równa wartości argumentu drugiego;
  • większe od 0 - gdy wartość argumentu pierwszego jest większa od argumentu drugiego.

Przykład

C/C++
#include <cstdio>
#include <cstdlib>

typedef int ElementT;

int porownaj( const ElementT * klucz, const ElementT * wartosc );
ElementT * wyszukaj( ElementT element, ElementT * tablica, int ilosc );

int main()
{
    ElementT tablica[] = { 1, 3, 5, 7, 8, 9, 10, 20, 50, 99 };
   
    ElementT iLiczba;
    printf( "Podaj liczbe: " );
    scanf( "%d", & iLiczba );
    ElementT * pWynik = wyszukaj( iLiczba, tablica, sizeof( tablica ) / sizeof( ElementT ) );
   
    if( pWynik )
         printf( "\nZnaleziono: %d\n", * pWynik );
    else
         printf( "\npWynik = NULL.\n" );
   
    return 0;
}

int porownaj( const ElementT * klucz, const ElementT * wartosc )
{
    if( * klucz < * wartosc )
         return - 1;
   
    if( * klucz > * wartosc )
         return 1;
   
    return 0;
}

ElementT * wyszukaj( ElementT element, ElementT * tablica, int ilosc )
{
    return reinterpret_cast < ElementT *>( bsearch( & element, tablica, ilosc, sizeof( element ),( int( * )( const void *, const void * ) ) porownaj ) );
}

Zagadnienia powiązane

binary_searchWykonuje algorytm binarnego przeszukiwania na posortowanym zakresie danych. (szablon funkcji)

Linki zewnętrzne