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

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

Οι στόχοι της δυαδικής αναζήτησης είναι:

  • να μπορείτε να απορρίψετε το μισό του πίνακα σε κάθε επανάληψη
  • ελαχιστοποιήστε τον αριθμό των στοιχείων που πρέπει να περάσουμε
  • αφήστε μας με μια τελική τιμή

Πάρτε για παράδειγμα την ακόλουθη σειρά ακέραιων αριθμών:

int array[] = { 1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71 };

Ας πούμε ότι προσπαθούμε να βρούμε την τιμή ευρετηρίου του αριθμού 7 σε αυτόν τον πίνακα. Υπάρχουν 17 στοιχεία συνολικά και οι τιμές ευρετηρίου κυμαίνονται από 0 έως 16.

Μπορούμε να δούμε ότι η τιμή του δείκτη του 7 είναι 4, καθώς είναι το πέμπτο στοιχείο του πίνακα.

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

Αρχικά, αποθηκεύουμε τις τιμές minκαι τις maxτιμές, όπως 0και 16.

int min = 0;int max = 16;

Τώρα πρέπει να βρούμε μια εικασία. Το πιο έξυπνο πράγμα που πρέπει να κάνετε είναι να μαντέψετε μια τιμή ευρετηρίου στη μέση του πίνακα.

Με την τιμή ευρετηρίου 0 έως 16 σε αυτόν τον πίνακα, η τιμή του μεσαίου ευρετηρίου αυτού του πίνακα θα είναι 8. Αυτό ισχύει για τον αριθμό 14.

// This will round down if the quotient is not an integer

int guess = (min + max) / 2;

Η εικασία μας είναι τώρα ίση με 8, που είναι 14 στον πίνακα, αφού array[8]είναι ίση με 14.

Εάν ο αριθμός που ψάχναμε ήταν 14, θα είχαμε τελειώσει!

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

Μετά την πρώτη επανάληψη, η αναζήτησή μας βρίσκεται τώρα εντός: 1, 3, 4, 6, 7, 8, 10, 13

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

Δεδομένου ότι η αρχική μας εικασία για το 14 ήταν μεγαλύτερη από 7, τώρα τη μειώνουμε κατά 1 και την αποθηκεύουμε σε max:

max = guess - 1; // max is now equal to 7, which is 13 in the array

Τώρα η αναζήτηση μοιάζει με αυτό:

 1, 3, 4, 6, 7, 8, 10, 13
min = 0max = 7guess = 3 

Επειδή η εικασία μας ήταν πολύ χαμηλή, απορρίπτουμε το κάτω μισό του πίνακα αυξάνοντας min, αντίθετα με αυτό που κάναμε προηγουμένως max:

min = guess + 1; // min is now 4

Μέχρι την επόμενη επανάληψη, έχουμε μείνει με:

 7, 8, 10, 13min = 4max = 7guess = 5

Δεδομένου ότι η τιμή ευρετηρίου 5 επιστρέφει 8, είμαστε πλέον ένας από τους στόχους μας. Επαναλαμβάνουμε τη διαδικασία ξανά, και μένουμε με:

 7min = 4max = 4guess = 4

Και μένουμε με μία μόνο τιμή, 4, ως το ευρετήριο του αριθμού στόχου που αναζητούσαμε, που ήταν 7

Ο σκοπός της δυαδικής αναζήτησης είναι να απαλλαγούμε από το μισό του πίνακα σε κάθε επανάληψη. Γι 'αυτό δουλεύουμε μόνο σε εκείνες τις τιμές στις οποίες έχει νόημα να συνεχίζουμε να μαντέψουμε.

Ο ψευδοκωδικός για αυτόν τον αλγόριθμο θα μοιάζει με αυτό:

  1. Αφήστε min = 0και αφήστε max = nπού nείναι η υψηλότερη δυνατή τιμή ευρετηρίου
  2. Βρείτε τον μέσο όρο minκαι max, στρογγυλοποιήστε προς τα κάτω, ώστε να είναι ακέραιος. Αυτό είναι δικό μαςguess
  3. Αν μαντέψαμε τον αριθμό, σταματήστε, το έχουμε!
  4. Εάν guessείναι πολύ χαμηλή, ορίστε minίσο με ένα περισσότερο απόguess
  5. Εάν guessείναι πολύ υψηλό, ορίστε maxίσο με ένα μικρότερο απόguess
  6. Επιστρέψτε στο δεύτερο βήμα.

Εδώ είναι μια λύση, γραμμένη σε C ++: