Namespaces
Variants

bsearch, bsearch_s

From cppreference.net
C
Algorithms
(C11)
bsearch bsearch_s
(C11)
Definiert in Header <stdlib.h>
void * bsearch ( const void * key, const void * ptr, size_t count, size_t size,
int ( * comp ) ( const void * , const void * ) ) ;
(1)
void * bsearch_s ( const void * key, const void * ptr, rsize_t count, rsize_t size,

int ( * comp ) ( const void * , const void * , void * ) ,

void * context ) ;
(2) (seit C11)
/*QVoid*/ * bsearch ( const void * key, /*QVoid*/ * ptr, size_t count, size_t size,
int ( * comp ) ( const void * , const void * ) ) ;
(3) (seit C23)
/*QVoid*/ * bsearch_s ( const void * key, /*QVoid*/ * ptr, rsize_t count, rsize_t size,

int ( * comp ) ( const void * , const void * , void * ) ,

void * context ) ;
(4) (seit C23)
1) Findet ein Element, das dem durch key referenzierten Element entspricht, in einem Array, auf das ptr zeigt. Das Array enthält count Elemente von je size Bytes und muss bezüglich key partitioniert sein, d.h. alle Elemente, die kleiner vergleichen, müssen vor allen Elementen erscheinen, die gleich vergleichen, und diese müssen vor allen Elementen erscheinen, die größer vergleichen als das Schlüsselobjekt. Ein vollständig sortiertes Array erfüllt diese Anforderungen. Die Elemente werden mittels der durch comp referenzierten Funktion verglichen. Das Verhalten ist undefiniert, wenn das Array nicht bereits bezüglich *key in aufsteigender Reihenfolge gemäß demselben Kriterium partitioniert ist, das comp verwendet.
2) Gleich wie (1) , mit der Ausnahme, dass der zusätzliche Zustandsparameter context an comp übergeben wird und dass die folgenden Fehler zur Laufzeit erkannt werden und die aktuell installierte Constraint-Handler -Funktion aufrufen:
  • count oder size größer als RSIZE_MAX sind
  • key , ptr oder comp ein Nullzeiger sind (sofern count nicht null ist)
Wie bei allen bounds-checked-Funktionen ist bsearch_s (und das entsprechende typgenerische Makro) (seit C23) nur garantiert verfügbar, wenn __STDC_LIB_EXT1__ durch die Implementierung definiert ist und wenn der Benutzer __STDC_WANT_LIB_EXT1__ auf die Integer-Konstante 1 setzt, bevor <stdlib.h> eingebunden wird.
3,4) Typgenerische Makros, die äquivalent zu (1) und (2) sind. Sei T ein unqualifizierter Objekttyp (einschließlich void ).
  • Wenn ptr vom Typ const T * ist, dann ist der Rückgabetyp const void * .
  • Andernfalls, wenn ptr vom Typ T * ist, dann ist der Rückgabetyp void * .
  • Andernfalls ist das Verhalten undefiniert.
Falls eine Makrodefinition für jede dieser generischen Funktionen unterdrückt wird, um auf eine tatsächliche Funktion zuzugreifen (z.B. wenn ( bsearch ) , ( bsearch_s ) oder ein Funktionszeiger verwendet wird), wird die tatsächliche Funktionsdeklaration (1) oder (2) sichtbar.

Wenn das Array mehrere Elemente enthält, die comp als gleich dem gesuchten Element anzeigen würde, dann ist nicht spezifiziert, welches Element die Funktion als Ergebnis zurückgibt.

Direkte Verwendungen der tatsächlichen Funktionen (1) und (2) sind veraltet.

(since C23)

Inhaltsverzeichnis

Parameter

key - Zeiger auf das zu suchende Element
ptr - Zeiger auf das zu untersuchende Array
count - Anzahl der Elemente im Array
size - Größe jedes Elements im Array in Bytes
comp - Vergleichsfunktion, die eine negative Ganzzahl zurückgibt, wenn das erste Argument kleiner als das zweite ist, eine positive Ganzzahl, wenn das erste Argument größer als das zweite ist, und null, wenn die Argumente äquivalent sind. key wird als erstes Argument übergeben, ein Element aus dem Array als zweites.

Die Signatur der Vergleichsfunktion sollte der folgenden entsprechen:

int cmp ( const void * a, const void * b ) ;

Die Funktion darf die übergebenen Objekte nicht modifizieren und muss bei Aufruf für dieselben Objekte konsistente Ergebnisse zurückgeben, unabhängig von deren Position im Array.

​

context - Zustand des Komparators (z.B. Sortierreihenfolge), der an comp als drittes Argument übergeben wird

Rückgabewert

1) Zeiger auf ein Element im Array, das gleich * key vergleicht, oder Nullzeiger, falls kein solches Element gefunden wurde.
2) Gleich wie (1) , außer dass der Nullzeiger auch bei Verletzungen der Laufzeitbedingungen zurückgegeben wird.
3,4) Gleich wie (1) und (2) jeweils, außer dass die CV-Qualifikation angepasst wird.

Hinweise

Trotz des Namens verlangen weder die C- noch die POSIX-Standards, dass diese Funktion mittels binärer Suche implementiert wird oder geben irgendwelche Komplexitätsgarantien.

Im Gegensatz zu anderen grenzprüfenden Funktionen behandelt bsearch_s Arrays mit der Größe Null nicht als Laufzeitbedingungsverletzung und gibt stattdessen "Element nicht gefunden" zurück (die andere Funktion, die Arrays mit der Größe Null akzeptiert, ist qsort_s ).

Bis bsearch_s verwendeten Benutzer von bsearch häufig globale Variablen, um den Zustand des Komparators darzustellen.

Beispiel

Diesen Code ausführen 
#include <stdlib.h>
#include <stdio.h>
struct data {
    int nr;
    char const *value;
} dat[] = {
    {1, "Foo"}, {2, "Bar"}, {3, "Hello"}, {4, "World"}
};
int data_cmp(void const *lhs, void const *rhs) 
{
    struct data const *const l = lhs;
    struct data const *const r = rhs;
    if (l->nr < r->nr) return -1;
    else if (l->nr > r->nr) return 1;
    else return 0;
    // return (l->nr > r->nr) - (l->nr < r->nr); // possible shortcut
    // return l->nr - r->nr; // erroneous shortcut (fails if INT_MIN is present)
}
int main(void) 
{
    struct data key = { .nr = 3 };
    struct data const *res = bsearch(&key, dat, sizeof dat / sizeof dat[0],
                                     sizeof dat[0], data_cmp);
    if (res) {
        printf("No %d: %s\n", res->nr, res->value);
    } else {
        printf("No %d not found\n", key.nr);
    }
}

Ausgabe: 

No 3: Hello

Referenzen

  • C17-Standard (ISO/IEC 9899:2018):
  • 7.22.5.1 Die bsearch-Funktion (S: 258)
  • K.3.6.3.1 Die bsearch_s-Funktion (S: 441-442)
  • C11-Standard (ISO/IEC 9899:2011):
  • 7.22.5.1 Die bsearch-Funktion (S. 355)
  • K.3.6.3.1 Die bsearch_s-Funktion (S. 608-609)
  • C99-Standard (ISO/IEC 9899:1999):
  • 7.20.5.1 Die bsearch-Funktion (S. 318-319)
  • C89/C90 Standard (ISO/IEC 9899:1990):
  • 4.10.5.1 Die bsearch-Funktion

Siehe auch

(C11)
sortiert eine Reihe von Elementen mit unspezifiziertem Typ
(Funktion)
C++-Dokumentation für bsearch