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

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

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

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

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

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

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

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

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

Αλγόριθμος Δυαδικής Αναζήτησης (Ψευδοκώδικας)

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

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Η ρουτίνα επιστρέφει τον δείκτη του στόχου σε περίπτωση επιτυχίας και -1 όταν η τιμή δεν υπάρχει. Επειδή το εύρος μειώνεται στο μισό σε κάθε πέρασμα, ο βρόχος εκτελείται το πολύ log₂(n) φορές.

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

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

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

1. Έχετε έναν πίνακα 10 ψηφίων και το στοιχείο 59 πρέπει να βρεθεί.
2. Όλα τα στοιχεία σημειώνονται με τον δείκτη από 0 έως 9. Τώρα, υπολογίζεται η μέση του πίνακα. Για να το κάνετε αυτό, παίρνετε τις τιμές που βρίσκονται στην αριστερή και τη δεξιά πλευρά του δείκτη και τις διαιρείτε με το 2. Το αποτέλεσμα είναι 4.5, αλλά εμείς παίρνουμε την τιμή κατώτατου ορίου. Επομένως, η μέση είναι 4.
3. Ο αλγόριθμος αφαιρεί όλα τα στοιχεία από τη μέση (4) στο χαμηλότερο όριο, επειδή το 59 είναι μεγαλύτερο από το 24, και τώρα ο πίνακας έχει μόνο 5 στοιχεία.
4. Τώρα, το 59 είναι μεγαλύτερο από το 45 και μικρότερο από το 63. Το μεσαίο είναι 7. Επομένως, η δεξιά τιμή του δείκτη γίνεται μεσαίο − 1, που ισούται με 6, και η αριστερή τιμή του δείκτη παραμένει η ίδια όπως πριν, που είναι 5.
5. Σε αυτό το σημείο, γνωρίζετε ότι το 59 έρχεται μετά το 45. Επομένως, ο αριστερός δείκτης, που είναι 5, γίνεται επίσης μεσαίος.
6. Αυτές οι επαναλήψεις συνεχίζονται έως ότου ο πίνακας μειωθεί σε ένα μόνο στοιχείο ή το στοιχείο που θα βρεθεί γίνει το μέσο του πίνακα.

Παράδειγμα 2

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

1. Έχετε μια σειρά από ταξινομημένες τιμές που κυμαίνονται από 2 έως 20 και πρέπει να εντοπίσετε το 18.
2. Ο μέσος όρος των κατώτερων και ανώτερων ορίων είναι (l + r) / 2 = 4. Η τιμή που αναζητείται είναι μεγαλύτερη από τη μέση τιμή, η οποία είναι 4.
3. Οι τιμές του πίνακα που είναι μικρότερες από τη μέση τιμή αφαιρούνται από την αναζήτηση και αναζητούνται τιμές που είναι μεγαλύτερες από τη μέση τιμή 4.
4. Αυτή είναι μια επαναλαμβανόμενη διαδικασία διαίρεσης μέχρι να βρεθεί το πραγματικό αντικείμενο προς αναζήτηση.

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

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

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

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

Δυαδική αναζήτηση έναντι γραμμικής αναζήτησης

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

Με λίγα λόγια, η δυαδική αναζήτηση είναι πολύ πιο γρήγορη σε μεγάλα ταξινομημένα δεδομένα, ενώ η γραμμική αναζήτηση είναι απλούστερη και η μόνη επιλογή όταν τα δεδομένα δεν είναι ταξινομημένα.

Συχνές Ερωτήσεις