Πριν μάθουμε τη δυαδική αναζήτηση, ας μάθουμε:
Τι είναι η Αναζήτηση;
Η αναζήτηση είναι ένα βοηθητικό πρόγραμμα που επιτρέπει στο χρήστη του να βρει έγγραφα, αρχεία, μέσα ή οποιοδήποτε άλλο είδος δεδομένων που διατηρείται μέσα σε μια βάση δεδομένων. Η αναζήτηση λειτουργεί με την απλή αρχή της αντιστοίχισης των κριτηρίων με τις εγγραφές και της εμφάνισής τους στον χρήστη. Με αυτόν τον τρόπο, λειτουργεί η πιο βασική λειτουργία αναζήτησης.
Τι είναι η δυαδική αναζήτηση;
Η δυαδική αναζήτηση είναι ένας προηγμένος τύπος αλγορίθμου αναζήτησης που βρίσκει και ανακτά δεδομένα από μια ταξινομημένη λίστα αντικειμένων. Η βασική αρχή λειτουργίας του περιλαμβάνει τη διαίρεση των δεδομένων στη λίστα στο μισό έως ότου εντοπιστεί και εμφανιστεί η απαιτούμενη τιμή στο χρήστη στο αποτέλεσμα αναζήτησης. Η δυαδική αναζήτηση είναι συνήθως γνωστή ως αναζήτηση μισού διαστήματος ή λογαριθμική αναζήτηση .
Σε αυτό το σεμινάριο αλγορίθμων, θα μάθετε:
- Τι είναι η Αναζήτηση;
- Τι είναι η δυαδική αναζήτηση;
- Πώς λειτουργεί η Δυαδική Αναζήτηση;
- Παράδειγμα Δυαδική Αναζήτηση
- Γιατί χρειαζόμαστε δυαδική αναζήτηση;
Πώς λειτουργεί η Δυαδική Αναζήτηση;
Η δυαδική αναζήτηση λειτουργεί με τον ακόλουθο τρόπο:
- Η διαδικασία αναζήτησης ξεκινά εντοπίζοντας το μεσαίο στοιχείο του ταξινομημένου πίνακα δεδομένων
- Μετά από αυτό, η τιμή κλειδιού συγκρίνεται με το στοιχείο
- Εάν η τιμή κλειδιού είναι μικρότερη από το μεσαίο στοιχείο, τότε οι αναζητήσεις αναλύουν τις ανώτερες τιμές στο μεσαίο στοιχείο για σύγκριση και αντιστοίχιση
- Σε περίπτωση που η τιμή κλειδιού είναι μεγαλύτερη από το μεσαίο στοιχείο, τότε αναζητά αναλύει τις χαμηλότερες τιμές στο μεσαίο στοιχείο για σύγκριση και αντιστοίχιση
Παράδειγμα Δυαδική Αναζήτηση
Ας δούμε το παράδειγμα ενός λεξικού. Εάν πρέπει να βρείτε μια συγκεκριμένη λέξη, κανείς δεν περνά από κάθε λέξη με διαδοχικό τρόπο, αλλά εντοπίζει τυχαία τις πλησιέστερες λέξεις για να αναζητήσει την απαιτούμενη λέξη.
Η παραπάνω εικόνα απεικονίζει τα εξής:
- Έχετε έναν πίνακα 10 ψηφίων και πρέπει να βρεθεί το στοιχείο 59.
- Όλα τα στοιχεία επισημαίνονται με το ευρετήριο από 0 - 9. Τώρα, υπολογίζεται το μέσο του πίνακα. Για να το κάνετε αυτό, παίρνετε τις αριστερές και δεξιότερες τιμές του ευρετηρίου και τις διαιρείτε με 2. Το αποτέλεσμα είναι 4,5, αλλά παίρνουμε την κατώτατη τιμή. Εξ ου και η μέση είναι 4.
- Ο αλγόριθμος πέφτει όλα τα στοιχεία από τη μέση (4) στο χαμηλότερο όριο, επειδή το 59 είναι μεγαλύτερο από 24, και τώρα ο πίνακας μένει μόνο με 5 στοιχεία.
- Τώρα, το 59 είναι μεγαλύτερο από 45 και λιγότερο από 63. Η μέση είναι 7. Ως εκ τούτου, η τιμή του δεξιού δείκτη γίνεται μέση - 1, που ισούται με 6 και η τιμή του αριστερού δείκτη παραμένει η ίδια όπως πριν, δηλαδή 5.
- Σε αυτό το σημείο, γνωρίζετε ότι το 59 έρχεται μετά το 45. Ως εκ τούτου, ο αριστερός δείκτης, που είναι 5, γίνεται επίσης μέσος.
- Αυτές οι επαναλήψεις συνεχίζονται έως ότου ο πίνακας μειωθεί σε ένα μόνο στοιχείο ή το στοιχείο που θα βρεθεί γίνει στη μέση του πίνακα.
Παράδειγμα 2
Ας δούμε το παρακάτω παράδειγμα για να κατανοήσουμε ότι η δυαδική αναζήτηση λειτουργεί
- Έχετε μια σειρά από ταξινομημένες τιμές που κυμαίνονται από 2 έως 20 και πρέπει να εντοπίσετε 18.
- Ο μέσος όρος των κατώτερων και ανώτερων ορίων είναι (l + r) / 2 = 4. Η τιμή που αναζητείται είναι μεγαλύτερη από τη μέση που είναι 4.
- Οι τιμές του πίνακα μικρότερες από τη μέση απορρίπτονται από την αναζήτηση και αναζητούνται τιμές μεγαλύτερες από τη μέση τιμή 4.
- Αυτή είναι μια επαναλαμβανόμενη διαδικασία διαίρεσης έως ότου βρεθεί το πραγματικό αντικείμενο προς αναζήτηση.
Γιατί χρειαζόμαστε δυαδική αναζήτηση;
Οι ακόλουθοι λόγοι καθιστούν τη δυαδική αναζήτηση καλύτερη επιλογή για χρήση ως αλγόριθμος αναζήτησης:
- Η δυαδική αναζήτηση λειτουργεί αποτελεσματικά σε ταξινομημένα δεδομένα ανεξάρτητα από το μέγεθος των δεδομένων
- Αντί να εκτελεί την αναζήτηση μέσω των δεδομένων σε μια ακολουθία, ο δυαδικός αλγόριθμος αποκτά τυχαία πρόσβαση στα δεδομένα για να βρει το απαιτούμενο στοιχείο. Αυτό καθιστά τους κύκλους αναζήτησης μικρότεροι και ακριβέστεροι.
- Η δυαδική αναζήτηση πραγματοποιεί συγκρίσεις των ταξινομημένων δεδομένων βάσει μιας αρχής παραγγελίας από τη χρήση συγκρίσεων ισότητας, οι οποίες είναι πιο αργές και ως επί το πλείστον ανακριβείς.
- Μετά από κάθε κύκλο αναζήτησης, ο αλγόριθμος διαιρεί το μέγεθος του πίνακα σε μισό, επομένως στην επόμενη επανάληψη θα λειτουργεί μόνο στο υπόλοιπο μισό του πίνακα
Περίληψη
- Η αναζήτηση είναι ένα βοηθητικό πρόγραμμα που επιτρέπει στο χρήστη του να αναζητά έγγραφα, αρχεία και άλλους τύπους δεδομένων. Η δυαδική αναζήτηση είναι ένας προηγμένος τύπος αλγορίθμου αναζήτησης που βρίσκει και ανακτά δεδομένα από μια ταξινομημένη λίστα στοιχείων.
- Η δυαδική αναζήτηση είναι συνήθως γνωστή ως αναζήτηση μισού διαστήματος ή λογαριθμική αναζήτηση
- Λειτουργεί χωρίζοντας τον πίνακα σε μισό σε κάθε επανάληψη που βρίσκεται κάτω από το απαιτούμενο στοιχείο.
- Ο δυαδικός αλγόριθμος παίρνει τη μέση του πίνακα διαιρώντας το άθροισμα των τιμών του δείκτη αριστερού και δεξιού με το 2. Τώρα, ο αλγόριθμος πέφτει είτε το κάτω είτε το ανώτερο όριο των στοιχείων από τη μέση του πίνακα, ανάλογα με το στοιχείο που θα βρεθεί .
- Ο αλγόριθμος αποκτά τυχαία πρόσβαση στα δεδομένα για να βρει το απαιτούμενο στοιχείο. Αυτό καθιστά τους κύκλους αναζήτησης μικρότεροι και ακριβέστεροι.
- Η δυαδική αναζήτηση πραγματοποιεί συγκρίσεις των ταξινομημένων δεδομένων βάσει μιας αρχής παραγγελίας από τη χρήση συγκρίσεων ισότητας που είναι αργές και ανακριβείς.
- Μια δυαδική αναζήτηση δεν είναι κατάλληλη για μη ταξινομημένα δεδομένα.