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

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

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

## Περιγραφή

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

Επειδή το διάνυσμα είναι σε αύξουσα σειρά, η τιμή του στοιχείου στη θέση i του διανύσματος θα είναι μικρότερη ή ίση από όλα τα στοιχεία δεξιά και μεγαλύτερη ή ίση από όλα τα στοιχεία αριστερά (η ισότητα μπορεί να προκύψει μόνο στην περίπτωση που υπάρχουν επαναλαμβανόμενες τιμές). Έτσι, αν σε μια σύγκριση, το κλειδί είναι μεγαλύτερο από το στοιχείο στη θέση i, δεν έχει νόημα να κάνουμε συγκρίσεις με τα στοιχεία που βρίσκονται σε θέση j\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)

## Δείτε επίσης
* Γραμμική αναζήτηση
* Δυαδικό δέντρο αναζήτησης

Κατηγορία:Αλγόριθμοι Διαίρει και Βασίλευε
Κατηγορία:Αλγόριθμοι αναζήτησης
Κατηγορία:Επιστήμη υπολογιστών