Πολύ συχνά, προγραμματιστές, ακόμη και αρχάριοι,αντιμέτωποι με το γεγονός ότι υπάρχει ένα σύνολο αριθμών στο οποίο πρέπει να βρείτε έναν συγκεκριμένο αριθμό. Αυτή η συλλογή ονομάζεται πίνακας. Και για να βρείτε το επιθυμητό στοιχείο σε αυτό, υπάρχει μια τεράστια ποικιλία τρόπων. Αλλά το απλούστερο μεταξύ αυτών μπορεί δικαίως να θεωρηθεί δυαδική αναζήτηση. Ποια είναι η δεδομένη μέθοδος; Και πώς να εφαρμόσετε δυαδική αναζήτηση; Το Pascal είναι το απλούστερο περιβάλλον για τη διοργάνωση ενός τέτοιου προγράμματος, επομένως θα το χρησιμοποιήσουμε για μελέτη.
Πρώτον, θα δούμε τα πλεονεκτήματα αυτής της μεθόδου, γιατί μπορούμε να καταλάβουμε
Итак, в чем же заключается принцип работы данного μέθοδος? Αξίζει να πούμε αμέσως ότι η δυαδική αναζήτηση δεν λειτουργεί σε κανένα πίνακα, αλλά μόνο σε ένα ταξινομημένο σύνολο αριθμών. Σε κάθε επόμενο βήμα, λαμβάνεται το μεσαίο στοιχείο του πίνακα (που σημαίνει τον αριθμό του στοιχείου). Εάν ο επιθυμητός αριθμός είναι μεγαλύτερος από τον μέσο όρο, τότε όλα όσα βρίσκονται στα αριστερά, δηλαδή λιγότερο από το μεσαίο στοιχείο, μπορούν να απορριφθούν και να μην αναζητηθούν εκεί. Αντίθετα, εάν είναι μικρότερο από το μέσο όρο - μεταξύ αυτών των αριθμών στα δεξιά, δεν μπορείτε να πραγματοποιήσετε αναζήτηση. Στη συνέχεια, επιλέγουμε μια νέα περιοχή αναζήτησης, όπου το πρώτο στοιχείο θα είναι το μεσαίο στοιχείο ολόκληρου του πίνακα και το τελευταίο θα παραμείνει το τελευταίο. Ο μέσος αριθμός της νέας περιοχής θα είναι ¼ ολόκληρου του τμήματος, δηλαδή (το τελευταίο στοιχείο + το μεσαίο στοιχείο ολόκληρου του πίνακα) / 2. Και πάλι εκτελείται η ίδια λειτουργία - σύγκριση με τον μέσο αριθμό του πίνακα. Εάν η επιθυμητή τιμή είναι μικρότερη από τον μέσο όρο, απορρίπτουμε τη δεξιά πλευρά και το κάνουμε επίσης μέχρι να βρεθεί αυτό το μεσαίο στοιχείο.
Φυσικά, είναι καλύτερο να δούμε ένα παράδειγμα για το πώς γράφεται η δυαδική αναζήτηση. Οποιοσδήποτε Pascal θα κάνει εδώ - η έκδοση δεν είναι σημαντική. Ας γράψουμε ένα απλό πρόγραμμα.
Θα περιέχει έναν πίνακα από το 1 έως το h που ονομάζεται"massiv", μεταβλητή που δηλώνει το κάτω όριο της αναζήτησης με το όνομα "niz", το άνω φράγμα με το όνομα "verh", ο μεσαίος όρος αναζήτησης με το όνομα "sredn". και ο απαιτούμενος αριθμός είναι "isk".
Έτσι, πρώτα εκχωρούμε τα άνω και κάτω όρια του διαστήματος αναζήτησης:
niz: = 1;
verh: = h + 1;
Στη συνέχεια οργανώνουμε τον κύκλο "ενώ το κατώτερο είναι μικρότερο από το ανώτερο όριο":
Ενώ niz <verh - 1 κάνω
αρχίσει
Σε κάθε βήμα, διαιρούμε το τμήμα με 2:
sredn: = (niz + verh) div 2; {χρησιμοποιήστε τη συνάρτηση div επειδή διαιρούμε χωρίς υπόλοιπο}
Κάθε φορά που ελέγχουμε. Εάν ο μέσος όρος είναι ίσος με τον επιθυμητό, διακόπτουμε τον βρόχο, αφού το απαιτούμενο στοιχείο έχει ήδη βρεθεί:
іf sredn = isk τότε σπάσε.
Εάν το μεσαίο στοιχείο του πίνακα είναι μεγαλύτερο από το επιθυμητό, απορρίψτε την αριστερή πλευρά, δηλαδή αντιστοιχίστε το μεσαίο στοιχείο ως το επάνω περίγραμμα:
αν massiv [sredn]> isk τότε verh: = sredn;
Και αν το αντίθετο, τότε το κάνουμε το κατώτερο όριο:
αλλιώς νιζ: = sredn;
τέλος;
Αυτό είναι το μόνο που θα υπάρχει στο πρόγραμμα.
Ας δούμε πώς θα μοιάζει στην πράξη η δυαδική μέθοδος. Ας πάρουμε έναν πίνακα όπως αυτός: 1, 3, 5, 7, 10, 12, 18 και αναζητήστε τον αριθμό 12 σε αυτόν.
Συνολικά, έχουμε 7 στοιχεία, οπότε το μεσαίο θα είναι το τέταρτο, η τιμή του είναι 7.
| 1 | 3 | 5 | 7 | 10 | 12 | 18 |
Επειδή το 12 είναι μεγαλύτερο από το 7, μπορούμε να απορρίψουμε τα στοιχεία 1,3 και 5. Τότε μας απομένουν 4 αριθμοί, τα 4/2 χωρίς υπόλοιπο είναι 2. Άρα, το νέο μεσαίο στοιχείο θα είναι 10.
| 7 | 10 | 12 | 18 |
Εδώ το μεσαίο στοιχείο είναι ήδη 12, αυτός είναι ο επιθυμητός αριθμός. Η εργασία ολοκληρώθηκε - βρέθηκε ο αριθμός 12.
