Πώς λειτουργεί ο αλγόριθμος δυαδικής αναζήτησης;

Η δυαδική αναζήτηση λειτουργεί αναλύοντας έναν ταξινομημένο πίνακα, διαιρώντας συνεχώς το εύρος αναζήτησης στη μέση.

1. Εκκίνηση: Ορίζονται τα αριστερά και δεξιά όρια του εύρους αναζήτησης (συνήθως η αρχή και το τέλος του πίνακα).
2. Σύγκριση: Υπολογίζεται η δείκτης του μέσου του εύρους. Η τιμή σε αυτό το δείκτη συγκρίνεται με το ζητούμενο στοιχείο.
3. Μείωση του εύρους:
   • Αν η τιμή στο μέσο ταιριάζει με το ζητούμενο, το στοιχείο βρέθηκε.
   • Αν η τιμή στο μέσο είναι μεγαλύτερη από το ζητούμενο, η αναζήτηση συνεχίζεται στο αριστερό μισό του εύρους. Ο δεξιός περιορισμός μετακινείται στο μέσο - 1.
   • Αν η τιμή στο μέσο είναι μικρότερη από το ζητούμενο, η αναζήτηση συνεχίζεται στο δεξί μισό του εύρους. Ο αριστερός περιορισμός μετακινείται στο μέσο + 1.
4. Επανάληψη: Τα βήματα 2 και 3 επαναλαμβάνονται μέχρι να βρεθεί το στοιχείο ή το εύρος αναζήτησης να γίνει κενό.

Η πολυπλοκότητα του αλγορίθμου είναι O(log n), που είναι πολύ πιο αποδοτικό από την γραμμική αναζήτηση για μεγάλους πίνακες.

Παράδειγμα υλοποίησης σε Python:

def binary_search(arr, target):
    """
    Υλοποίηση δυαδικής αναζήτησης.
    Δέχεται έναν ταξινομημένο πίνακα και την τιμή που αναζητάται.
    Επιστρέφει το δείκτη του στοιχείου ή -1 αν δεν βρεθεί.
    """
    αριστερά, δεξιά = 0, len(arr) - 1

    while αριστερά <= δεξιά:
        μέσο = (αριστερά + δεξιά) // 2  # Υπολογισμός δείκτη μέσου
        μέσο_τιμή = arr[μέσο]      # Λήψη τιμής στο μέσο

        if μέσο_τιμή == target:
            return μέσο  # Βρέθηκε το στοιχείο
        elif μέσο_τιμή < target:
            αριστερά = μέσο + 1  # Αναζήτηση δεξιά
        else: # μέσο_τιμή > target
            δεξιά = μέσο - 1 # Αναζήτηση αριστερά

    return -1 # Το στοιχείο δεν βρέθηκε