Πίνακας περιεχομένων:
Ορισμός - Τι σημαίνει δυαδική αναζήτηση;
Ένας δυαδικός αλγόριθμος αναζήτησης χρησιμοποιείται για να εντοπίσει τη θέση μιας συγκεκριμένης τιμής που περιέχεται σε μια ταξινομημένη συστοιχία. Εργάζοντας με την αρχή της διάσπασης και κατακράτησης, αυτός ο αλγόριθμος αναζήτησης μπορεί να είναι αρκετά γρήγορος, αλλά η προειδοποίηση είναι ότι τα δεδομένα πρέπει να είναι σε μια ταξινομημένη μορφή. Λειτουργεί με την εκκίνηση της αναζήτησης στη μέση της συστοιχίας και την εργασία που κατεβαίνει κάτω από το πρώτο κάτω ή το πάνω μισό της ακολουθίας. Εάν η διάμεση τιμή είναι χαμηλότερη από την τιμή στόχο, αυτό σημαίνει ότι η αναζήτηση πρέπει να πάει υψηλότερη, αν όχι, τότε πρέπει να κοιτάξει πάνω στο φθινόπωρο του πίνακα.
Μια δυαδική αναζήτηση είναι επίσης γνωστή ως αναζήτηση μισού διαστήματος ή λογαριθμική αναζήτηση.
Η Techopedia εξηγεί τη δυαδική αναζήτηση
Μια δυαδική αναζήτηση είναι μια γρήγορη και αποτελεσματική μέθοδος εξεύρεσης συγκεκριμένης τιμής στόχου από ένα σύνολο παραγγελιών. Αρχίζοντας στη μέση της ταξινομημένης λίστας, μπορεί να μειώσει αποτελεσματικά το χώρο αναζήτησης στο μισό, καθορίζοντας αν θα ανέλθει ή θα κατέβει η λίστα με βάση τη μέση τιμή σε σύγκριση με την τιμή στόχο.
Για παράδειγμα, με τιμή στόχου 8 και χώρο αναζήτησης από 1 έως 11:
- Η μέση / μεσαία τιμή βρίσκεται και ο δείκτης βρίσκεται εκεί, ο οποίος στην περίπτωση αυτή είναι 6.
- Ο στόχος του 8 συγκρίνεται με το 6. Δεδομένου ότι το 6 είναι μικρότερο από 8, ο στόχος πρέπει να βρίσκεται στο υψηλότερο μισό.
- Ο δείκτης μετακινείται στην επόμενη τιμή (7) και συγκρίνεται με τον στόχο. Είναι μικρότερο, επομένως ο δείκτης μετακινείται στην επόμενη υψηλότερη τιμή.
- Ο δείκτης είναι τώρα σε 8. Συγκρίνοντας αυτό με το στόχο, είναι μια ακριβής αντιστοίχιση, οπότε ο στόχος έχει βρεθεί.
Χρησιμοποιώντας δυαδική αναζήτηση, ο στόχος έπρεπε μόνο να συγκριθεί με τρεις τιμές. Σε σύγκριση με τη διεξαγωγή μιας γραμμικής αναζήτησης, θα είχε ξεκινήσει από την πρώτη τιμή και θα κινηθεί προς τα επάνω, χρειάζεται να συγκρίνει τον στόχο με οκτώ τιμές. Μια δυαδική αναζήτηση είναι δυνατή μόνο με μια σειρά δεδομένων που έχει παραγγελθεί. εάν τα δεδομένα είναι τυχαία διατεταγμένα, τότε μια γραμμική αναζήτηση θα αποφέρει αποτελέσματα όλη την ώρα ενώ μια δυαδική αναζήτηση πιθανότατα θα κολλήσει σε έναν άπειρο βρόχο.
