====== bsearch() ======

''bsearch()'' ist in der ''[[c:lib:stdlib:start|stdlib]]'' definiert, die in C über ''stdlib.h'', bzw in C++ über ''cstdlib'' eingebunden wird.

===== Funktion =====

''bsearch()'' durchsucht ein Array per [[algo:binarysearch|binärer Suche]]

===== Signatur =====

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

**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:
<code cpp>
#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;
}
</code>

**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.

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

**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:

<code cpp>
  ...
  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;
  ...
</code> 

**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 =====

[[c:lib:stdlib:]]: [[qsort()]]