Αλγόριθμος δυαδικής αναζήτησης με EXAMPLE

Πριν μάθουμε Δυαδική αναζήτηση, ας μάθουμε:

Τι είναι η Αναζήτηση;

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

Τι είναι η δυαδική αναζήτηση;

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

Πώς λειτουργεί η δυαδική αναζήτηση;

Η δυαδική αναζήτηση λειτουργεί με τον ακόλουθο τρόπο:

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

Παράδειγμα δυαδικής αναζήτησης

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

Η παραπάνω εικόνα δείχνει τα εξής:

Έχετε έναν πίνακα 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 αναζητούνται.
Αυτή είναι μια επαναλαμβανόμενη διαδικασία διαίρεσης μέχρι να βρεθεί το πραγματικό αντικείμενο προς αναζήτηση.

Γιατί χρειαζόμαστε δυαδική αναζήτηση;

Οι ακόλουθοι λόγοι καθιστούν τη δυαδική αναζήτηση καλύτερη επιλογή για χρήση ως αλγόριθμος αναζήτησης:

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

Μάθετε το επόμενο σεμινάριο μας για Γραμμική αναζήτηση: Python, C++ Παράδειγμα

Περίληψη

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