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

Η δυαδική αναζήτηση είναι ένας αλγόριθμος για την εύρεση ενός στοιχείου σε μια ταξινομημένη λίστα με λογαριθμική πολυπλοκότητα O(log n). Λειτουργεί σύμφωνα με την αρχή "διαίρει και βασίλευε":

1. Ορίζεται το μεσαίο στοιχείο της λίστας.
2. Αν το ζητούμενο στοιχείο είναι ίσο με το μεσαίο, η αναζήτηση τερματίζεται.
3. Αν το ζητούμενο στοιχείο είναι μικρότερο από το μεσαίο, η αναζήτηση συνεχίζεται στο αριστερό μισό της λίστας.
4. Αν είναι μεγαλύτερο, στο δεξί μισό.

Η διαδικασία επαναλαμβάνεται αναδρομικά ή επαναληπτικά μέχρι να βρεθεί το στοιχείο ή να εξαντληθεί η περιοχή αναζήτησης.

Παράδειγμα σε Go:

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        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 // στοιχείο δεν βρέθηκε
}