Δυαδική αναζήτηση — αλγόριθμος, χρονική πολυπλοκότητα και κώδικας

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

Σε μια αύξουσα λίστα, ο κανόνας είναι απλός: αν η μεσαία τιμή είναι μικρότερη από τον στόχο, ψάχνεις δεξιά· αν είναι μεγαλύτερη, ψάχνεις αριστερά. Επειδή το εύρος μικραίνει κάθε φορά περίπου στο μισό, η δυαδική αναζήτηση εκτελείται σε χρόνο $O(\log n)$.

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

Χρησιμοποίησε την παρακάτω ταξινομημένη λίστα:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

Έστω ότι ο στόχος είναι το $31$.

Ξεκινάς με όλο το εύρος. Η μεσαία τιμή είναι το $24$. Εφόσον $31 > 24$, όλα όσα βρίσκονται αριστερά του $24$ μπορούν να απορριφθούν, οπότε η αναζήτηση συνεχίζεται στο

$$[31, 39, 45, 52]$$

Τώρα η μεσαία τιμή είναι το $39$. Εφόσον $31 < 39$, όλα όσα βρίσκονται δεξιά του $39$ μπορούν να απορριφθούν, οπότε το εύρος γίνεται

$$[31]$$

Τώρα η μεσαία τιμή είναι το $31$, άρα η αναζήτηση σταματά. Η χρήσιμη ιδέα δεν είναι μόνο ότι βρέθηκε ο στόχος. Σε δύο συγκρίσεις, το υποψήφιο εύρος έπεσε από $9$ τιμές σε $1$.

Γιατί η δυαδική αναζήτηση είναι $O(\log n)$

Κάθε σύγκριση αποκλείει περίπου τους μισούς από τους υποψήφιους που απομένουν. Μετά από ένα βήμα, απομένουν περίπου $n/2$ στοιχεία. Μετά από δύο βήματα, απομένουν περίπου $n/4$. Μετά από $k$ βήματα, το μέγεθος που απομένει είναι περίπου

$$\frac{n}{2^k}$$

Η αναζήτηση ολοκληρώνεται όταν αυτή η ποσότητα γίνει περίπου $1$, άρα ο αριθμός των βημάτων ικανοποιεί τη σχέση

$$2^k \approx n$$

Παίρνοντας $\log_2$ και στα δύο μέρη, προκύπτει

$$k \approx \log_2 n$$

Γι’ αυτό η δυαδική αναζήτηση κλιμακώνεται καλά. Μια γραμμική αναζήτηση μπορεί να χρειαστεί έως και $n$ ελέγχους, αλλά η δυαδική αναζήτηση χρειάζεται μόνο τόσους ελέγχους όσους απαιτούνται για να υποδιπλασιάζεται συνεχώς το εύρος.

Παράδειγμα κώδικα δυαδικής αναζήτησης

Ακολουθεί μια τυπική επαναληπτική έκδοση σε Python: