Seitenleiste

Wiki

Community

Funktionen

Speicher

Konventierung

Zufall

System

Enviroment

Suchen/Ersetzen

int Arithmetik

Multibyte-Chars

bsearch()

bsearch() ist in der stdlib definiert, die in C über stdlib.h, bzw in C++ über cstdlib eingebunden wird.

Funktion

bsearch() durchsucht ein Array per binärer Suche

Signatur

#include <stdlib.h>
void * bsearch( void const * key, void * array, size_t elementCount, size_t size, int (*compare)(const void *, const void *) );

key: Das Element, dass gesucht wird
array: Zeiger auf das erste Element des zu durchsuchenden Arrays
elementCount: Anzahl der Elemente im Array
size: Größe eines einzelnen Elementes
compare: Vergleichsfunktion, um zwei Elemente miteinander zu vergleichen.

Return Value: Zeiger auf das gefundene Element innerhalb des Arrays oder NULL. Passt key auf mehrere Elemente im Array, so ist es möglich, dass es weitere Element vor, wie auch nach dem gefundenen Element gibt.

Die Vergleichsfunktion gibt -1 zurück, wenn der linke Parameter vor dem rechten Parameter einsortiert wurde, 0, falls der linke und rechte Parameter gleichwertig sind und 1, falls der rechte Parameter vor dem linken einsortiert wurde. Sie entspricht damit der Funktion, die für qsort() verwendet werden kann.

Fehlerquellen

-

Beispiel

Einmaliges Element suchen

In diesem Beispiel (eine Abwandlung des Beispiels aus qsort() wird ein Array von Personen nach deren Alter sortiert und anschließend wird nach einer Person gesucht, die 40 Jahre alt ist. Es gibt im sortierten Array nur eine Person, die 40 Jahre alt ist und somit wird diese auch gefunden:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
struct Person
{
  char * FirstName;
  char * FamilyName;
  int    Age;
};
 
int compareAge( void const * lhs, void const * rhs )
{
  struct Person * left  = ((struct Person *) lhs);
  struct Person * right = ((struct Person *) rhs);
 
  if( left->Age < right->Age ) return -1;
  if( left->Age > right->Age ) return 1;
 
  return 0;
}
 
int main ( void )
{
  struct Person figures[] = { { "Max", "Mustermann", 40 }
                            , { "Erika", "Mustermann", 38 }
//                            , { "Jane", "Doe", 32 }
                            , { "Erika", "Gabler", 38 }
//                            , { "John", "Doe", 34 }
                            , { "Erika", "Mustermann", 35 }
                            , NULL };
 
  int const elements = 4;
  int const ageKey   = 40;
 
  int i = 0;
 
  printf( "Originalreihenfolge:\n" );
  for( i = 0; i < elements; ++i )
    printf( "%s, %s (%d)\n", figures[i].FamilyName, figures[i].FirstName, figures[i].Age );
 
  qsort( figures, elements, sizeof( struct Person ), compareAge );
 
  printf( "\nsortierte Reihenfolge:\n" );
  for( i = 0; i < elements; ++i )
    printf( "%s, %s (%d)\n", figures[i].FamilyName, figures[i].FirstName, figures[i].Age );
 
  printf( "\nSuche eine Person, die %d Jahre alt ist:\n", ageKey );
 
  struct Person key;
  key.Age = ageKey;;
 
  struct Person * result = bsearch( &key, figures, elements, sizeof( struct Person ), compareAge );
 
  if( result )
    printf( "gefunden: %s, %s (%d)\n", result->FamilyName, result->FirstName, result->Age );
  else
    printf( "nichts gefunden\n" );
 
  return EXIT_SUCCESS;
}

Ausgabe

Originalreihenfolge:
Mustermann, Max (40)
Mustermann, Erika (38)
Gabler, Erika (38)
Mustermann, Erika (35)

sortierte Reihenfolge:
Mustermann, Erika (35)
Mustermann, Erika (38)
Gabler, Erika (38)
Mustermann, Max (40)

Suche eine Person, die 40 Jahre alt ist:
gefunden: Mustermann, Max (40)

mehrfach vorhandenes Element suchen

Im Quelltext wird nur eine Zahl geändert, so dass wir nun nach Personen suchen, die 38 Jahre alt sind.

  ...
  int const ageKey   = 38;    // <- hier stand vorher 40
  ... 

Ausgabe

Originalreihenfolge:
Mustermann, Max (40)
Mustermann, Erika (38)
Gabler, Erika (38)
Mustermann, Erika (35)

sortierte Reihenfolge:
Mustermann, Erika (35)
Mustermann, Erika (38)
Gabler, Erika (38)
Mustermann, Max (40)

Suche eine Person, die 38 Jahre alt ist:
gefunden: Gabler, Erika (38)

Es wird also die zweite 38jährige, Erika Gabler, gefunden.

Im Quelltext sind noch John und Jane Doe auskommentiert. Diese fügen wir nun ein und vergrößern damit das zu durchsuchende Array auf 6 Elemente:

  ...
  struct Person figures[] = { { "Max", "Mustermann", 40 }
                            , { "Erika", "Mustermann", 38 }
                            , { "Jane", "Doe", 32 }           // Kommentar entfernt
                            , { "Erika", "Gabler", 38 }
                            , { "John", "Doe", 34 }           // Kommentar entfernt
                            , { "Erika", "Mustermann", 35 }
                            , NULL };
 
  int const elements = 6;                                     // <- hier stand zuvor 4
  int const ageKey   = 38;
  ...

Ausgabe

Originalreihenfolge:
Mustermann, Max (40)
Mustermann, Erika (38)
Doe, Jane (32)
Gabler, Erika (38)
Doe, John (34)
Mustermann, Erika (35)

sortierte Reihenfolge:
Doe, Jane (32)
Doe, John (34)
Mustermann, Erika (35)
Mustermann, Erika (38)
Gabler, Erika (38)
Mustermann, Max (40)

Suche eine Person, die 38 Jahre alt ist:
gefunden: Mustermann, Erika (38)

Wir erkennen, dass obwohl die Suchanfrage identisch ist, ein anderes Ergebnis herauskommt: statt Erika Gabler finden wir diesmal Erika Mustermann.
Ein eindeutiges Ergebnis ist nur dann möglich, wenn das Suchkriterium wirklich einmalig im Array vorkommt. Ansonsten muss man solange schrittweise nach vorne gehen, bis das Suchkriterium nicht mehr erfüllt ist (oder das erste Element des Arrays erreicht ist) und anschließend, um alle Elemente abzuarbeiten, schrittweise Element für Element durchgegangen wird, bis das Suchkriterium nicht mehr erfüllt ist (oder das letzte Element des Arrays erreicht ist).

siehe auch