bsearch, bsearch_s

 

C

Compiler-Unterstützung

Sprache

Header

Typunterstützung

Programm-Dienstprogramme

Unterstützung für variable Funktionsargumente

Fehlerbehandlung

Dynamische Speicherverwaltung

Bibliothek für Zeichenketten

Algorithmen

Numerik

Datums- und Zeitdienstprogramme

Ein-/Ausgabeunterstützung

Lokalisierungsunterstützung

Unterstützung für Nebenläufigkeit (C11)

Technische Spezifikationen

Symbolindex

 

Algorithmen

qsortqsort_s (C11)

bsearchbsearch_s (C11)

 

Definiert im 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) Sucht ein Element, das mit dem Element, auf das key zeigt, übereinstimmt, in einem Array, auf das ptr zeigt. Das Array enthält count Elemente mit jeweils size Bytes und muss bezüglich key partitioniert sein, d.h. alle Elemente, die kleiner als der Schlüssel sind, müssen vor allen Elementen erscheinen, die gleich dem Schlüssel sind, und diese wiederum müssen vor allen Elementen erscheinen, die größer als der Schlüssel sind. Ein vollständig sortiertes Array erfüllt diese Anforderungen. Die Elemente werden mit der Funktion verglichen, auf die comp zeigt. Das Verhalten ist undefiniert, wenn das Array nicht bereits bezüglich *key in aufsteigender Reihenfolge gemäß dem gleichen Kriterium partitioniert ist, das comp verwendet.

2) Gleiches wie (1), außer dass das zusätzliche Zustandsargument context an comp übergeben wird und die folgenden Fehler zur Laufzeit erkannt und die aktuell installierte Constraint-Handler-Funktion aufgerufen wird.

• count oder size ist größer als RSIZE_MAX
• key, ptr oder comp ist ein Nullzeiger (es sei denn, count ist Null)

Wie bei allen grenzgeprüften Funktionen ist bsearch_s (und das entsprechende typt-generische Makro)(seit C23) nur garantiert verfügbar, wenn __STDC_LIB_EXT1__ von der Implementierung definiert wird und wenn der Benutzer __STDC_WANT_LIB_EXT1__ vor dem Einbinden von <stdlib.h> auf die Ganzzahlkonstante 1 setzt.

3,4) Typt-generische Makros, die äquivalent zu (1) bzw. (2) sind. Sei T ein unqualifizierter Objekttyp (einschließlich void).

• Wenn ptr vom Typ const T* ist, ist der Rückgabetyp const void*.
• Andernfalls, wenn ptr vom Typ T* ist, ist der Rückgabetyp void*.
• Andernfalls ist das Verhalten undefiniert.

Wenn eine Makrodefinition jeder dieser generischen Funktionen unterdrückt wird, um auf eine tatsächliche Funktion zuzugreifen (z. B. wenn (bsearch), (bsearch_s) verwendet wird oder ein Funktionszeiger), wird die tatsächliche Funktionsdeklaration (1) oder (2) sichtbar.

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

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

(seit C23)

Parameter

key	-	Zeiger auf das zu suchende Element
ptr	-	Zeiger auf das zu untersuchende Array
zählt	-	Anzahl der Elemente im Array
size	-	Größe jedes Elements im Array in Bytes
comp	-	Vergleichsfunktion, die einen negativen ganzzahligen Wert zurückgibt, wenn das erste Argument *kleiner* als das zweite ist, einen positiven ganzzahligen Wert, 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 äquivalent zu Folgendem sein  int cmp(const void *a, const void *b); Die Funktion darf die ihr übergebenen Objekte nicht ändern und muss konsistente Ergebnisse zurückgeben, wenn sie für dieselben Objekte aufgerufen wird, unabhängig von ihrer Position im Array. ​
Kontext	-	Zustand des Comparators (z. B. Kollationssequenz), der als drittes Argument an comp übergeben wird.

Rückgabewert

1) Zeiger auf ein Element im Array, das mit *key übereinstimmt, oder ein Nullzeiger, wenn ein solches Element nicht gefunden wurde.

2) Gleiches wie (1), außer dass auch bei Laufzeitbeschränkungsverletzungen ein Nullzeiger zurückgegeben wird.

3,4) Gleiches wie (1) und (2), außer dass die cv-Qualifizierung angepasst wird.

Anmerkungen

Trotz des Namens verlangen weder der C- noch der POSIX-Standard, dass diese Funktion mittels Binärsuche implementiert wird, oder machen irgendwelche Komplexitätsgarantien.

Im Gegensatz zu anderen grenzgeprüften Funktionen behandelt bsearch_s Arrays von Nullgröße nicht als Laufzeitbeschränkungsverletzung, sondern meldet stattdessen ein nicht gefundenes Element (die andere Funktion, die Arrays von Nullgröße akzeptiert, ist qsort_s).

Bis bsearch_s verwendeten Benutzer von bsearch oft globale Variablen, um den Zustand des Comparators darzustellen.

Beispiel

Führen Sie diesen Code aus

#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 Funktion bsearch (S. 258)

• K.3.6.3.1 Die Funktion bsearch_s (S. 441-442)

• C11-Standard (ISO/IEC 9899:2011)

• 7.22.5.1 Die Funktion bsearch (S. 355)

• K.3.6.3.1 Die Funktion bsearch_s (S. 608-609)

• C99-Standard (ISO/IEC 9899:1999)

• 7.20.5.1 Die Funktion bsearch (S. 318-319)

• C89/C90-Standard (ISO/IEC 9899:1990)

• 4.10.5.1 Die Funktion bsearch

Siehe auch

qsortqsort_s (C11)	sortiert einen Bereich von Elementen unbekannten Typs (Funktion)
C++ Dokumentation für bsearch