Βικιπαίδεια

Δυαδική αναζήτηση: Διαφορά μεταξύ των αναθεωρήσεων

Περιήγηση ιστορικού διαδραστικά
← Προηγούμενη διαφοράΕπόμενη διαφορά →
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
ΟπτικήΚώδικας wiki
Χωρίς σύνοψη επεξεργασίας
Vevek (συζήτηση | συνεισφορές)
435 επεξεργασίες
Χωρίς σύνοψη επεξεργασίας
Γραμμή 1:
{{Πηγές|27|05|2011}}<br>
 
'''Δυαδική αναζήτηση''' ονομάζεται ένας [[αναδρομή|αναδρομικός]] [[αλγόριθμος]] αναζήτησης ενός στοιχείου (το λεγόμενο ''στοιχείο-κλειδί'') σε έναν ταξινομημένο μονοδιάστατο πίνακα. Εν γένει, η αναζήτηση σε έναν μη ταξινομημένο πίνακα γίνεται σε χρόνο γραμμικό ως προς το μέγεθος της εισόδου, συγκρίνοντας ένα προς ένα τα στοιχεία της εισόδου με το κλειδί. Όμως, η δυαδική αναζήτηση στηρίζεται στο γεγονός ότι ο πίνακας είναι ταξινομημένος, μειώνοντας έτσι σημαντικά τον αριθμό των συγκρίσεων που απαιτούνται.
 
Εναλλακτικά μπορεί να χρησιμοποιηθεί κάποια άλλη [[δομή δεδομένων]], αλλά είναι απαραίτητο αυτή να υποστηρίζει την τυχαία προσπέλαση σε σταθερό χρόνο. Για παράδειγμα, η δυαδική αναζήτηση δεν μπορεί να εφαρμοστεί σε μια δομή δεδομένων όπως η [[Λίστα (αφηρημένος τύπος δεδομένων)|λίστα]].
'''Δυαδική αναζήτηση''' ονομάζεται ένας [[αναδρομή|αναδρομικός]] [[αλγόριθμος]] αναζήτησης ενός στοιχείου (το λεγόμενο ''στοιχείο-κλειδί'') σε μια ταξινομημένη <!--στατική -->[[δομή δεδομένων]]. Ο αλγόριθμος στηρίζεται στο γεγονός ότι η δομή δεδομένων είναι ταξινομημένη μειώνοντας σημαντικά τον αριθμό γενικά των συκρίσεων που απαιτούνται, ώστε να είναι πιο σύντομος από τη [[γραμμική αναζήτηση]]. Σε αντιστοιχία με την καθημερινή ζωή η δυαδική αναζήτηση αντιστοιχεί στην εύρεση μιας σελίδας σε ένα βιβλίο, ενώ η γραμμική αναζήτηση στην εύρεση μιας σελίδας σε μία στοίβα από σελίδες που δεν είναι σε σειρά.
 
==Περιγραφή==
==Αρχή λειτουργίας==
 
Ο αλγόριθμος δέχεται ως είσοδο έναν ταξινομημένο μονοδιάστατο πίνακα (διάνυσμα) και μια τιμή που ονομάζεται ''κλειδί''. Επιστρέφει την θέση του κλειδιού στο διάνυσμα ή μια ειδική ένδειξη για να ενημερώσει ότι το κλειδί δεν υπάρχει στο διάνυσμα, αν αυτή είναι η περίπτωση. Το διάνυσμα μπορεί να είναι ταξινομημένο είτε σε αύξουσα σειρά είτε σε φθίνουσα, αλλά και στις δύο περιπτώσεις ο αλγόριθμος μπορεί να λειτουργήσεις σωστά (με τις κατάλληλες τροποποιήσεις) και στον ίδιο χρόνο. Λόγω της ισοδυναμίας αυτής, μπορούμε χωρίς βλάβη της γενικότητας να θεωρήσουμε ότι το διάνυσμα είναι ταξινομημένο κατά αύξουσα σειρά.
Στη δυαδική αναζήτηση η δομή δεδομένων χωρίζεται σε τρία τμήματα, στο στοιχείο της μεσαίας θέσης, στο τμήμα των στοιχείων που προηγούνται του μεσαίου και στο τμήμα των στοιχείων που έπονται του μεσαίου. Επειδή η δομή είναι ταξινομημένη, η σύκριση του στοιχείου-κλειδιού με το μεσαίο θα δείξει σε ποιό τμήμα ανήκει το στοιχείο-κλειδί. Αν ισούται με το μεσαίο, τότε η αναζήτηση έληξε, αλλιώς ανάλογα με το είδος της ταξινόμησης (αύξουσα ή φθίνουσα) ο αλγόριθμος καλείται αναδρομικά για ένα από τα άλλα δύο τμήματα.
 
Επειδή το διάνυσμα είναι ταξινομημένο, η τιμή του στοιχείου στη θέση i του διανύσματος θα είναι μικρότερη από όλα τα στοιχεία δεξιά και μεγαλύτερη από όλα τα στοιχεία αριστερά (στην περίπτωση που δεν έχουμε επαναλαμβανόμενες τιμές). Έτσι, αν σε μια σύγκριση, το κλειδί είναι μεγαλύτερο από το στοιχείο στη θέση i, δεν έχει νόημα να κάνουμε συγκρίσεις με τα στοιχεία που βρίσκονται σε θέση j<i (δηλαδή, αριστερά από τη θέση i). Αυτήν ακριβώς την ιδιότητα εκμεταλλεύεται η δυαδική αναζήτηση, ώστε να μειώσει κατά το δυνατό τις συγκρίσεις που κάνει.
===Ακραίες περιπτώσεις===▼
 
Αρχικά, το εύρος των θέσεων στις οποίες μπορεί να βρίσκεται το στοιχείο με τιμή ίση με το κλειδί είναι το μεγαλύτερο δυνατό. Δηλαδή, αρχικά ο αλγόριθμος θεωρεί ότι το κλειδί μπορεί να βρίσκεται οπουδήποτε μέσα στο διάνυσμα.
Ο αλγόριθμος όπως περιγράφτηκε λειτουργεί καλά, αν το στοιχείο-κλειδί υπάρχει στη δομή και υπάρχει μόνο μία φορά.
# Ξεκινά συγκρίνοντας το κλειδί με την τιμή του στοιχείου που βρίσκεται στο μέσο του διανύσματος.
# Αν είναι ίσα, τότε ο αλγόριθμος τερματίζει επιστρέφοντας τη θέση αυτή.
# Αν το κλειδί είναι μεγαλύτερο, τότε μειώνει το εύρος στο δεξί-μισό τμήμα του προηγούμενου τμήματος που εξέταζε και επαναλαμβάνει το πρώτο βήμα όχι για όλο το διάνυσμα, αλλά μόνο για το τμήμα του διανύσματος που επέλεξε.
# Αν το κλειδί είναι μικρότερο, τότε μειώνει το εύρος στο αριστερό-μισό τμήμα του προηγούμενου τμήματος που εξέταζε και επαναλαμβάνει το πρώτο βήμα όχι για όλο το διάνυσμα, αλλά μόνο για το τμήμα του διανύσματος που επέλεξε.
 
Μετά από έναν πεπερασμένο αριθμό βημάτων, ο αλγόριθμος είτε θα βρει τη ζητούμενη θέση, είτε θα μειώσει το εύρος της αναζήτησης στο μηδέν, που σημαίνει ότι το κλειδί δεν βρέθηκε στο διάνυσμα, και θα επιστρέψει την αντίστοιχη ένδειξη.
Αν το στοιχείο κλειδί δεν υπάρχει στη δομή δεν εκτελείται η αναζήτηση, ή αν δε γνωρίζουμε αν υπάρχει, τότε θα πρέπει να τροποποιήσουμε τον αλγόριθμο ώστε να σταματάει και όταν καταλήξει σε ένα στοιχείο που δεν ισούται με το στοιχείο κλειδί.
 
▲===Ακραίες περιπτώσεις===
 
Αν υπάρχει περίπτωση το στοιχείο-κλειδί να υπάρχει περισσότερες φορές και χρειάζεται να επιστραφούν όλες οι θέσεις, τότε ο αλγόριθμος χρειάζεται επιπλέον τροποποίηση.
 
==Χρονική πολυπλοκότητα==
 
Η χρονική πολυπλοκότητα του αλγόριθμου είναι λογαριθμική ως προς το μέγεθος της εισόδου. Έστω ότι το διάνυσμα της εισόδου είναι μεγέθους n (έχει n στοιχεία) και έστω T(n) ο χρόνος που χρειάζεται στη χειρότερη περίπτωση (όπου το κλειδί δεν υπάρχει στο διάνυσμα) για να βρει τη θέση του κλειδιού, ψάχοντας σε όλο το διάνυσμα. Και έστω ότι η σύγκριση παίρνει σταθερό χρόνο c. Τότε,
:<math>T(n) =
\begin{cases}
c & \mbox{if } n=0\\
T \left( \lfloor \frac{n}{2} \rfloor \right)+c &\mbox{if } n>0
\end{cases}
</math>
 
Η λύση της αναδρομικής αυτής εξίσωσης είναι
:<math>T(n) =c \cdot \log n +c = O(\log n)</math>
 
== Δείτε επίσης ==
* [[Γραμμική αναζήτηση]]
 
{{Αλγόριθμος-επέκταση}}
Ανακτήθηκε από "https://el.wikipedia.org/wiki/Δυαδική_αναζήτηση"