Η δυαδική αναζήτηση είναι ένας από τους ευκολότερους τρόπους εύρεσης ενός στοιχείου σε έναν πίνακα

Πολύ συχνά, οι προγραμματιστές, ακόμα και οι αρχάριοι, αντιμετωπίζουν το γεγονός ότι υπάρχει ένας αριθμός αριθμών στον οποίο είναι απαραίτητο να βρεθεί ένας ορισμένος αριθμός. Αυτή η συλλογή ονομάζεται συστοιχία. Και για να βρείτε το σωστό στοιχείο σε αυτό, υπάρχουν πολλοί τρόποι. Αλλά το πιο απλό από αυτά είναι η δυαδική αναζήτηση. Ποια είναι η μέθοδος; Και πώς να υλοποιήσετε μια δυαδική αναζήτηση; Το Pascal είναι το απλούστερο περιβάλλον για την οργάνωση ενός τέτοιου προγράμματος, οπότε θα το χρησιμοποιήσουμε για μελέτη.

Πρώτον, θα αναλύσουμε ποια είναι τα πλεονεκτήματα αυτής της μεθόδου, τελικά, έτσι ώστε να κατανοήσουμε, Ποιο είναι το σημείο στη μελέτη αυτού του θέματος. Υποθέστε λοιπόν ότι υπάρχει ένας πίνακας με διάσταση τουλάχιστον 100000000 στοιχείων, στην οποία πρέπει να βρείτε ένα συγκεκριμένο. Φυσικά, αυτό το πρόβλημα μπορεί εύκολα να λυθεί με μια απλή γραμμική αναζήτηση, στην οποία χρησιμοποιούμε ένα βρόχο για να συγκρίνουμε το επιθυμητό στοιχείο με όλα εκείνα που υπάρχουν στη συστοιχία. Το πρόβλημα είναι ότι η εφαρμογή αυτής της ιδέας θα πάρει πολύ χρόνο. Σε ένα απλό πρόγραμμα Pascal για πολλές διαδικασίες και με τρεις γραμμές του κύριου κειμένου, δεν θα το παρατηρήσετε, αλλά όταν ξεκινάτε περισσότερα ή λιγότερο μεγάλα έργα με πολλή διακλάδωση και καλή λειτουργικότητα, το τελικό πρόγραμμα θα φορτωθεί πάρα πολύ. Ειδικά αν ο υπολογιστής έχει κακή απόδοση. Επομένως, υπάρχει μια δυαδική αναζήτηση, η οποία μειώνει τον χρόνο αναζήτησης τουλάχιστον δύο φορές.

Λοιπόν, ποια είναι η αρχή αυτής της μεθόδου; Αμέσως αξίζει να πούμε ότι η δυαδική αναζήτηση δεν λειτουργεί σε κανέναν πίνακα, αλλά μόνο σε ένα ταξινομημένο σύνολο αριθμών. Σε κάθε επόμενο βήμα, λαμβάνεται το μέσο στοιχείο του πίνακα (αναφέρεται στον αριθμό στοιχείου). Αν ο επιθυμητός αριθμός είναι μεγαλύτερος από τον μέσο όρο, τότε όλα που βρίσκονται στα αριστερά, δηλαδή λιγότερο από το μέσο στοιχείο, μπορούν να απορριφθούν και να μην αναζητηθούν εκεί. Αντίθετα, εάν είναι μικρότερος από τον μέσο όρο, μεταξύ των αριθμών στα δεξιά, δεν μπορείτε να τα αναζητήσετε. Στη συνέχεια, θα επιλέξουμε μια νέα περιοχή αναζήτησης, όπου το πρώτο στοιχείο θα είναι το μεσαίο στοιχείο ολόκληρου του πίνακα, και το τελευταίο θα παραμείνει το τελευταίο. Ο μέσος αριθμός της νέας περιοχής θα είναι ¼ του συνόλου του τομέα, δηλαδή (το τελευταίο στοιχείο + το μέσο στοιχείο του συνόλου του πίνακα) / 2. Και πάλι, εκτελείται η ίδια λειτουργία - σύγκριση με τον μέσο αριθμό του πίνακα. Αν η επιθυμητή τιμή είναι μικρότερη από τον μέσο όρο, απορρίψτε τη δεξιά πλευρά και κάντε την ίδια μέχρι να βρεθεί αυτό το μεσαίο στοιχείο.

Φυσικά, ο καλύτερος τρόπος να εξετάσουμε το παράδειγμα είναι πώς να γράψουμε μια δυαδική αναζήτηση. Ο Pascal εδώ είναι κατάλληλος για όλους - η έκδοση δεν είναι σημαντική. Ας γράψουμε ένα απλό πρόγραμμα.

Θα έχει έναν πίνακα από 1 έως h που ονομάζεται "massiv", μια μεταβλητή που υποδηλώνει ένα χαμηλότερο όριο αναζήτησης, που ονομάζεται "niz", ένα ανώτερο όριο που ονομάζεται "verh", το μεσαίο στοιχείο αναζήτησης είναι "sredn". Και ο απαιτούμενος αριθμός είναι "isk".

Έτσι, ορίστε πρώτα τα ανώτερα και κατώτερα όρια του διαστήματος αναζήτησης:

Niz: = 1;
Verh: = h + 1.

Στη συνέχεια οργανώνουμε τον κύκλο "ενώ το κάτω μέρος είναι μικρότερο από το ανώτατο όριο":

Ενώ το niz Ξεκινήστε

Σε κάθε βήμα, διαιρέστε το τμήμα κατά 2:

Sredn: = (niz + verh) div 2. {Χρησιμοποιήστε τη λειτουργία div επειδή διαιρούμε το υπόλοιπο}

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

Εάν το sredn = isk τότε σπάσει.

Εάν το μεσαίο στοιχείο του πίνακα είναι μεγαλύτερο από αυτό που ψάχνουμε, απορρίπτουμε την αριστερή πλευρά, δηλαδή, εκχωρούμε το μεσαίο στοιχείο στο άνω όριο:

Αν το μαζικό [sredn]> isk τότε verh: = sredn;

Και αν το αντίθετο, τότε το κάνουμε το κατώτερο όριο:

Αλλιώς niz: = sredn;
Τέλος;

Αυτό είναι όλο που θα είναι στο πρόγραμμα.

Ας αναλύσουμε πώς θα φανεί η δυαδική μέθοδος στην πράξη. Πάρτε μια τέτοια διάταξη: 1, 3, 5, 7, 10, 12, 18 και αναζητήστε τον αριθμό 12 σε αυτό.

Συνολικά, έχουμε 7 στοιχεία, οπότε ο μέσος όρος θα είναι ο τέταρτος, η αξία του 7.

Δεδομένου ότι το 12 είναι μεγαλύτερο από 7, τα στοιχεία 1,3 και 5 μπορούν να απορριφθούν. Στη συνέχεια, έχουμε 4 αριθμούς αριστερά, 4/2 χωρίς το υπόλοιπο να είναι 2. Έτσι, το νέο μεσαίο στοιχείο θα είναι 10.

Από το 12 είναι περισσότερα από 10, απορρίπτουμε 7. Μόνο 10, 12 και 18 έχουν απομείνει.

Εδώ το μέσο στοιχείο είναι ήδη 12, αυτός είναι ο απαιτούμενος αριθμός. Η εργασία έχει ολοκληρωθεί - ο αριθμός 12 βρίσκεται.