Ο δυαδικός αλγόριθμος αναζήτησης είναι ένας πιο αποτελεσματικός τρόπος αναζήτησης ενός συγκεκριμένου στοιχείου σε μια ταξινομημένη λίστα. Σε αντίθεση με τη γραμμική αναζήτηση, η οποία ελέγχει τα στοιχεία διαδοχικά, η δυαδική αναζήτηση χωρίζει τη λίστα στα μισά και συγκρίνει το στοιχείο στόχο με το μεσαίο στοιχείο. Αυτή η διαδικασία επαναλαμβάνεται μέχρι να βρεθεί το στοιχείο προορισμού ή η περιοχή αναζήτησης να γίνει άδεια.
Πως δουλεύει
- Ξεκινήστε με ολόκληρη την ταξινομημένη λίστα.
- Βρείτε το μεσαίο στοιχείο της τρέχουσας περιοχής αναζήτησης.
- Συγκρίνετε το μεσαίο στοιχείο με την τιμή στόχο.
- Εάν το μεσαίο στοιχείο ισούται με την τιμή στόχο, η αναζήτηση είναι επιτυχής.
- Εάν το μεσαίο στοιχείο είναι μεγαλύτερο από τον στόχο, πραγματοποιήστε αναζήτηση στο αριστερό μισό του εύρους.
- Εάν το μεσαίο στοιχείο είναι μικρότερο από τον στόχο, πραγματοποιήστε αναζήτηση στο δεξί μισό του εύρους.
- Επαναλάβετε τα βήματα 2-6 μέχρι να βρεθεί το στοιχείο-στόχος ή η περιοχή αναζήτησης να γίνει άδεια.
Παράδειγμα
Ας εξετάσουμε μια ταξινομημένη λίστα ακεραίων και θέλουμε να βρούμε τον αριθμό 34 χρησιμοποιώντας δυαδική αναζήτηση.
Ταξινομημένη λίστα: {12, 23, 34, 45, 56, 67, 89, 90}
- Ξεκινήστε με ολόκληρη τη λίστα.
- Μεσαίο στοιχείο: 56(θέση 4). Σύγκριση με 34.
- Το 56 είναι μεγαλύτερο από 34. Αναζήτηση στο αριστερό μισό.
- Νέο μεσαίο στοιχείο: 23(θέση 1). Σύγκριση με 34.
- Το 23 είναι μικρότερο από το 34. Αναζήτηση στο δεξί μισό.
- Νέο μεσαίο στοιχείο: 45(θέση 3). Σύγκριση με 34.
- Το 45 είναι μεγαλύτερο από 34. Αναζήτηση στο αριστερό μισό.
- Νέο μεσαίο στοιχείο: 34(θέση 2). Ο στόχος βρέθηκε.
Παράδειγμα κώδικα σε C++
Στο συγκεκριμένο παράδειγμα, η binarySearch
συνάρτηση χρησιμοποιείται για την εύρεση του αριθμού 34 σε μια ταξινομημένη λίστα ακεραίων. Το αποτέλεσμα θα είναι η θέση 34 στη λίστα(οι θέσεις ξεκινούν από το 0) ή -1 εάν ο αριθμός δεν βρεθεί.