Die Funktion bsearch () in C ++ führt eine binäre Suche eines Elements in einem Array von Elementen durch und gibt einen Zeiger auf das Element zurück, wenn es gefunden wird.
Für die Funktion bsearch () müssen alle Elemente, die kleiner als das Element sind, links davon im Array gesucht werden.
Ebenso müssen sich alle Elemente, die größer als das zu durchsuchende Element sind, im Array rechts davon befinden. Diese Anforderung ist erfüllt, wenn das Array in aufsteigender Reihenfolge sortiert ist.
bsearch () Prototyp
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* vergleiche) (const void *, const void *));
Die Funktion ist in der Header-Datei definiert.
Die Funktion bsearch () sucht nach Schlüsseln in der Array-Basis. Alle Elemente, die kleiner als der Schlüssel sind, müssen in der Array-Basis davor stehen. Ebenso müssen alle Elemente, die größer als der Schlüssel sind, danach in der Basis erscheinen.
Um die Suche durchzuführen, ruft die Funktion bsearch () die Funktion auf, indem sie mit key als erstem Argument und einem Element aus dem Array als zweitem Argument vergleicht.
bsearch () Parameter
- Taste: Zeiger auf das zu suchende Element
- base: Zeiger auf das erste Element des Arrays
- num: Anzahl der Elemente im Array
- Größe: Größe in Bytes jedes Elements im Array
- compare: Ein Zeiger auf eine Funktion, die zwei Elemente vergleicht. Es kehrt zurück
- eine negative Ganzzahl, wenn das erste Argument kleiner als das zweite ist
- eine positive ganze Zahl, wenn das erste Argument größer als das zweite ist
- Null, wenn beide Argumente gleich sind
Der Schlüssel wird als erstes Argument übergeben, und ein Element aus dem Array wird als zweites Argument übergeben. Der Prototyp der Vergleichsfunktion sieht folgendermaßen aus:
int compare (const void * a, const void * b);
bsearch () Rückgabewert
Die Funktion bsearch () gibt Folgendes zurück:
- Zeiger auf das gefundene Element. Wenn mehr als ein übereinstimmendes Element gefunden wird, ist nicht angegeben, welche Elementadresse die Funktion als Ergebnis zurückgibt.
- Nullzeiger, wenn das Element nicht gefunden wird.
Beispiel 1: Wie funktioniert die Funktion bsearch ()?
#include #include using namespace std; int compare(const void* a, const void* b) ( const int* x = (int*) a; const int* y = (int*) b; return (*x - *y); ) int main() ( const int num = 10; int arr(num) = (5,9,10,14,16,19,21,26,29,31); int key1 = 10; int *p1 = (int*)bsearch(&key1,arr,num,sizeof(int),compare); if(p1 == NULL) cout << key1 << " not found " << endl; else cout << key1 << " found at position " << (p1-arr) << endl; int key2 = 15; int *p2 = (int*)bsearch(&key2,arr,num,sizeof(int),compare); if(p2 == NULL) cout << key2 << " not found " << endl; else cout << key2 << " found at position " << (p2-arr) << endl; return 0; )
Wenn Sie das Programm ausführen, lautet die Ausgabe wie folgt:
10 gefunden an Position 2 15 nicht gefunden
Beispiel 2: Wie funktioniert die Funktion bsearch () für mehr als ein übereinstimmendes Element?
#include #include using namespace std; int compare(const void* a, const void* b) ( const int* x = (int*) a; const int* y = (int*) b; return (*x - *y); ) int main() ( const int num = 10; int arr(num) = (2,3,5,7,8,10,14,14,14,15); int key = 14; int *p = (int*)bsearch(&key,arr,num,sizeof(int),compare); if(p == NULL) cout << key << " not found " << endl; else /* 14 occurs at position 6,7 and 8*/ cout << key << " found at position " << (p-arr) << endl; return 0; )
Wenn Sie das Programm ausführen, ist eine mögliche Ausgabe:
14 an Position 7 gefunden
