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

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

Πρώτον, θα αναλύσουμε ποια είναι τα πλεονεκτήματα αυτής της μεθόδου, τελικά, έτσι ώστε να κατανοήσουμε,

ποιο είναι το σημείο μελέτης αυτού του θέματος. Υποθέστε λοιπόν ότι υπάρχει ένας πίνακας με διάσταση τουλάχιστον 100000000 στοιχείων, στην οποία πρέπει να βρείτε ένα συγκεκριμένο. Φυσικά, αυτό το πρόβλημα μπορεί εύκολα να λυθεί με μια απλή γραμμική αναζήτηση, στην οποία θα χρησιμοποιήσουμε τον κύκλο για να συγκρίνουμε το επιθυμητό στοιχείο με όλα εκείνα που υπάρχουν στη συστοιχία. Το πρόβλημα είναι ότι η εφαρμογή αυτής της ιδέας θα διαρκέσει πολύ. Σε ένα απλό πρόγραμμα 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 επειδή διαιρούμε το υπόλοιπο}

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

αν sredn = isk στη συνέχεια σπάσει?

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

αν massiv [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 βρίσκεται.