Δυαδική αναζήτηση

Δυαδική αναζήτηση ονομάζεται ένας αναδρομικός αλγόριθμος αναζήτησης ενός στοιχείου (το λεγόμενο στοιχείο-κλειδί) σε έναν ταξινομημένο μονοδιάστατο πίνακα. Ο αλγόριθμος αυτός χρησιμοποιεί την τεχνική Διαίρει και Βασίλευε. Εν γένει, η αναζήτηση σε έναν μη ταξινομημένο πίνακα γίνεται σε χρόνο γραμμικό ως προς το μέγεθος της εισόδου, συγκρίνοντας ένα προς ένα τα στοιχεία της εισόδου με το κλειδί. Όμως, η δυαδική αναζήτηση στηρίζεται στο γεγονός ότι ο πίνακας είναι ταξινομημένος, μειώνοντας έτσι σημαντικά τον αριθμό των συγκρίσεων που απαιτούνται.

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

Περιγραφή

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

Επειδή το διάνυσμα είναι σε αύξουσα σειρά, η τιμή του στοιχείου στη θέση i του διανύσματος θα είναι μικρότερη ή ίση από όλα τα στοιχεία δεξιά και μεγαλύτερη ή ίση από όλα τα στοιχεία αριστερά (η ισότητα μπορεί να προκύψει μόνο στην περίπτωση που υπάρχουν επαναλαμβανόμενες τιμές). Έτσι, αν σε μια σύγκριση, το κλειδί είναι μεγαλύτερο από το στοιχείο στη θέση i, δεν έχει νόημα να κάνουμε συγκρίσεις με τα στοιχεία που βρίσκονται σε θέση j<i (δηλαδή, αριστερά από τη θέση i). Αυτήν ακριβώς την ιδιότητα εκμεταλλεύεται η δυαδική αναζήτηση, ώστε να μειώσει κατά το δυνατό τις συγκρίσεις που κάνει.

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

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

Μετά από έναν πεπερασμένο αριθμό βημάτων, ο αλγόριθμος είτε θα βρει τη ζητούμενη θέση, είτε θα μειώσει το εύρος της αναζήτησης στο μηδέν, που σημαίνει ότι το κλειδί δεν βρέθηκε στο διάνυσμα, και θα επιστρέψει την αντίστοιχη ένδειξη.

Ψευδοκώδικας

   Δυαδική_αναζήτηση(Δ[1...n], κλειδί, i, j){
       Αν (j < i) τότε
           επίστρεψε "Δεν βρέθηκε" και τερμάτισε.
       μ = $\lfloor (i+j)/2\rfloor$
       Αν (κλειδί = Δ[μ]) τότε
           επίστρεψε μ και τερμάτισε
       αλλιώς αν (κλειδί > Δ[μ]) τότε
           Δυαδική_αναζήτηση(Δ[1...n], κλειδί, μ, j)
       αλλιώς
           Δυαδική_αναζήτηση(Δ[1...n], κλειδί, i, μ)
   }

Ο παραπάνω ψευδοκώδικας περιγράφει την αναζήτηση του κλειδιού στο διάνυσμα Δ μεγέθους n, μεταξύ των θέσεων i και j. Για να γίνει η αναζήτηση σε όλο το διάνυσμα, θέτουμε i=1 και j=n και εκτελούμε τον αλγόριθμο.

Ακραίες περιπτώσεις

Αν υπάρχει περίπτωση το στοιχείο-κλειδί να υπάρχει περισσότερες φορές και χρειάζεται να επιστραφούν όλες οι θέσεις, τότε ο αλγόριθμος χρειάζεται επιπλέον τροποποίηση.

Χρονική πολυπλοκότητα

Η χρονική πολυπλοκότητα του αλγόριθμου είναι λογαριθμική ως προς το μέγεθος της εισόδου. Έστω ότι το διάνυσμα της εισόδου είναι μεγέθους n (έχει n στοιχεία) και έστω T(n) ο χρόνος που χρειάζεται στη χειρότερη περίπτωση (όπου το κλειδί δεν υπάρχει στο διάνυσμα) για να βρει τη θέση του κλειδιού, ψάχνοντας σε όλο το διάνυσμα. Και έστω ότι η σύγκριση παίρνει σταθερό χρόνο c. Τότε,

$T(n)={\begin{cases}c&{\mbox{if }}n=0\\T\left(\lfloor {\frac {n}{2}}\rfloor \right)+c&{\mbox{if }}n>0\end{cases}}$

Η λύση της αναδρομικής αυτής εξίσωσης είναι

$T(n)=c\cdot \log n+c=O(\log n)$

Δείτε επίσης

• Γραμμική αναζήτηση
• Δυαδικό δέντρο αναζήτησης