Αλγόριθμος δυαδικής αναζήτησης (Binary Search) σε C++- Επεξήγηση, Παράδειγμα και Κώδικας

Ο δυαδικός αλγόριθμος αναζήτησης είναι ένας πιο αποτελεσματικός τρόπος αναζήτησης ενός συγκεκριμένου στοιχείου σε μια ταξινομημένη λίστα. Σε αντίθεση με τη γραμμική αναζήτηση, η οποία ελέγχει τα στοιχεία διαδοχικά, η δυαδική αναζήτηση χωρίζει τη λίστα στα μισά και συγκρίνει το στοιχείο στόχο με το μεσαίο στοιχείο. Αυτή η διαδικασία επαναλαμβάνεται μέχρι να βρεθεί το στοιχείο προορισμού ή η περιοχή αναζήτησης να γίνει άδεια.

Πως δουλεύει

1. Ξεκινήστε με ολόκληρη την ταξινομημένη λίστα.
2. Βρείτε το μεσαίο στοιχείο της τρέχουσας περιοχής αναζήτησης.
3. Συγκρίνετε το μεσαίο στοιχείο με την τιμή στόχο.
4. Εάν το μεσαίο στοιχείο ισούται με την τιμή στόχο, η αναζήτηση είναι επιτυχής.
5. Εάν το μεσαίο στοιχείο είναι μεγαλύτερο από τον στόχο, πραγματοποιήστε αναζήτηση στο αριστερό μισό του εύρους.
6. Εάν το μεσαίο στοιχείο είναι μικρότερο από τον στόχο, πραγματοποιήστε αναζήτηση στο δεξί μισό του εύρους.
7. Επαναλάβετε τα βήματα 2-6 μέχρι να βρεθεί το στοιχείο-στόχος ή η περιοχή αναζήτησης να γίνει άδεια.

Παράδειγμα

Ας εξετάσουμε μια ταξινομημένη λίστα ακεραίων και θέλουμε να βρούμε τον αριθμό 34 χρησιμοποιώντας δυαδική αναζήτηση.

Ταξινομημένη λίστα: {12, 23, 34, 45, 56, 67, 89, 90}

1. Ξεκινήστε με ολόκληρη τη λίστα.
2. Μεσαίο στοιχείο: 56(θέση 4). Σύγκριση με 34.
3. Το 56 είναι μεγαλύτερο από 34. Αναζήτηση στο αριστερό μισό.
4. Νέο μεσαίο στοιχείο: 23(θέση 1). Σύγκριση με 34.
5. Το 23 είναι μικρότερο από το 34. Αναζήτηση στο δεξί μισό.
6. Νέο μεσαίο στοιχείο: 45(θέση 3). Σύγκριση με 34.
7. Το 45 είναι μεγαλύτερο από 34. Αναζήτηση στο αριστερό μισό.
8. Νέο μεσαίο στοιχείο: 34(θέση 2). Ο στόχος βρέθηκε.

Παράδειγμα κώδικα σε C++

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

Στο συγκεκριμένο παράδειγμα, η binarySearch συνάρτηση χρησιμοποιείται για την εύρεση του αριθμού 34 σε μια ταξινομημένη λίστα ακεραίων. Το αποτέλεσμα θα είναι η θέση 34 στη λίστα(οι θέσεις ξεκινούν από το 0) ή -1 εάν ο αριθμός δεν βρεθεί.