Ποιος αλγόριθμος έχει λογαριθμική πολυπλοκότητα O(log n);

Ο αλγόριθμος δυαδικής αναζήτησης (ή διχοτομική αναζήτηση) έχει λογαριθμική χρονική πολυπλοκότητα O(log n).

Αρχή λειτουργίας της δυαδικής αναζήτησης:

1. Απαιτεί έναν ταξινομημένο πίνακα (ή λίστα).
2. Σε κάθε βήμα, συγκρίνει το ζητούμενο στοιχείο με το στοιχείο στο μέσο του τρέχοντος εύρους αναζήτησης.
3. Αν τα στοιχεία ταιριάζουν, η αναζήτηση ολοκληρώνεται.
4. Αν το ζητούμενο στοιχείο είναι μικρότερο από το μέσο, η αναζήτηση συνεχίζεται στο αριστερό μισό του εύρους.
5. Αν το ζητούμενο στοιχείο είναι μεγαλύτερο από το μέσο, η αναζήτηση συνεχίζεται στο δεξί μισό του εύρους.
6. Το εύρος αναζήτησης μειώνεται στο μισό σε κάθε βήμα.

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

# Συνάρτηση δυαδικής αναζήτησης
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_val = arr[mid]

        if mid_val == target:
            return mid  # Βρέθηκε το στοιχείο, επιστρέφει το δείκτη
        elif mid_val < target:
            low = mid + 1  # Αγνοεί το αριστερό μισό
        else:
            high = mid - 1  # Αγνοεί το δεξί μισό

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

# Παράδειγμα χρήσης
# ταξινομημένη_λίστα = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# στόχος = 23
# αποτέλεσμα = binary_search(ταξινομημένη_λίστα, στόχος)
# if αποτέλεσμα != -1:
#     print(f"Βρέθηκε το στοιχείο στη θέση: {αποτέλεσμα}")
# else:
#     print("Δεν βρέθηκε το στοιχείο")

Η λογαριθμική πολυπλοκότητα οφείλεται στο γεγονός ότι ο αριθμός των ενεργειών είναι ανάλογος με το λογάριθμο του μεγέθους των εισερχόμενων δεδομένων (n), καθώς σε κάθε βήμα, ο χώρος αναζήτησης μειώνεται στο μισό.