Η συνάρτηση bsearch () στο C ++ εκτελεί μια δυαδική αναζήτηση ενός στοιχείου σε μια σειρά στοιχείων και επιστρέφει έναν δείκτη στο στοιχείο εάν βρεθεί.
Η συνάρτηση bsearch () απαιτεί να αναζητηθούν όλα τα στοιχεία λιγότερο από το στοιχείο στα αριστερά του στον πίνακα.
Ομοίως, όλα τα στοιχεία μεγαλύτερα από το προς αναζήτηση στοιχείο πρέπει να βρίσκονται στα δεξιά του πίνακα. Αυτή η απαίτηση πληρούται εάν ο πίνακας ταξινομηθεί με αύξουσα σειρά.
bsearch () πρωτότυπο
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* σύγκριση) (const void *, const void *));
Η συνάρτηση ορίζεται στο αρχείο κεφαλίδας.
Η συνάρτηση bsearch () αναζητά κλειδί στη βάση πίνακα. Όλα τα στοιχεία λιγότερο από το κλειδί πρέπει να εμφανίζονται πριν από τη βάση του πίνακα. Ομοίως, όλα τα στοιχεία μεγαλύτερα από το κλειδί πρέπει να εμφανίζονται μετά τη βάση τους.
Προκειμένου να εκτελεστεί η αναζήτηση, η συνάρτηση bsearch () πραγματοποιεί μια σειρά από κλήσεις προς τη συνάρτηση που υποδεικνύεται από σύγκριση με το κλειδί ως το πρώτο όρισμα και ένα στοιχείο από τον πίνακα ως το δεύτερο όρισμα.
bsearch () Παράμετροι
- κλειδί: Δείκτης στο στοιχείο προς αναζήτηση
- βάση: Δείκτης στο πρώτο στοιχείο του πίνακα
- αριθμός: Αριθμός στοιχείου στον πίνακα
- size: Μέγεθος σε byte κάθε στοιχείου στον πίνακα
- σύγκριση: Ένας δείκτης σε μια συνάρτηση που συγκρίνει δύο στοιχεία. Επιστρέφει
- αρνητικό ακέραιο εάν το πρώτο όρισμα είναι μικρότερο από το δεύτερο
- ένα θετικό ακέραιο εάν το πρώτο όρισμα είναι μεγαλύτερο από το δεύτερο
- μηδέν εάν και τα δύο επιχειρήματα είναι ίδια
Το κλειδί μεταφέρεται ως πρώτο όρισμα και ένα στοιχείο από τον πίνακα περνά ως το δεύτερο όρισμα. Το πρωτότυπο της λειτουργίας σύγκρισης μοιάζει με:
int membandingkan (const void * a, const void * b);
bsearch () Τιμή επιστροφής
Η συνάρτηση bsearch () επιστρέφει:
- Δείκτης στο στοιχείο που βρέθηκε. Εάν βρεθούν περισσότερα από ένα στοιχεία που ταιριάζουν, τότε δεν έχει καθοριστεί ποια διεύθυνση του στοιχείου θα επιστρέψει η συνάρτηση ως αποτέλεσμα.
- Null δείκτη εάν το στοιχείο δεν βρεθεί.
Παράδειγμα 1: Πώς λειτουργεί η λειτουργία 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; )
Όταν εκτελείτε το πρόγραμμα, η έξοδος θα είναι:
10 βρέθηκαν στη θέση 2 15 δεν βρέθηκαν
Παράδειγμα 2: Πώς λειτουργεί η λειτουργία 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) = (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; )
Όταν εκτελείτε το πρόγραμμα, μια πιθανή έξοδος θα είναι:
14 βρέθηκαν στη θέση 7
