Η δυαδική αναζήτηση βρίσκει ένα στόχο σε έναν ταξινομημένο πίνακα διαιρώντας επανειλημμένα το εύρος αναζήτησης στη μέση. Κάθε σύγκριση αποκλείει το ήμισυ των υπόλοιπων στοιχείων, δίνοντας χρόνο O(log n).
Κοίταξε το μεσαίο στοιχείο. Αν ισούται με τον στόχο, τελείωσες. Αν ο στόχος είναι μικρότερος, αναζήτησε το αριστερό ήμισυ· αν είναι μεγαλύτερος, αναζήτησε το δεξί ήμισυ. Επανάλαβε μέχρι να βρεθεί ή το εύρος να είναι κενό.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2 # middle index
if arr[mid] == target:
return mid # found it
elif arr[mid] < target:
lo = mid + 1 # discard left half
else:
hi = mid - 1 # discard right half
return -1 # not present
binary_search([1, 3, 5, 7, 9], 7) # -> 3
Search 7 in [1,3,5,7,9]
lo=0 hi=4 mid=2 -> 5 < 7 => lo=3
lo=3 hi=4 mid=3 -> 7 == 7 => return 3
Το input πρέπει να είναι ταξινομημένο — διαφορετικά τα αποτελέσματα είναι χωρίς νόημα. Προσέχ λάθη κατά ένα στα lo/hi και υπερχείλιση ακεραίων σε ορισμένες γλώσσες (χρησιμοποίησε lo + (hi-lo)//2).
Η μείωση του χώρου αναζήτησης στη μέση μετατρέπει μια αναζήτηση με ένα εκατομμύριο στοιχεία σε ~20 συγκρίσεις.
Το μοτίβο διαίρει-και-βασίλευε πίσω του εμφανίζεται και πάλι σε δέντρα, βάσεις δεδομένων και αναρίθμητα προβλήματα συνεντεύξεων.
Η γνώση της μιας δύσκολης απαίτησής της — ταξινομημένο input — σε κρατά μακριά από ένα κλασικό λεπτό σφάλμα.