Δυαδική αναζήτηση στο Python: Μια οπτική εισαγωγή

καλως ΗΡΘΑΤΕ

Σε αυτό το άρθρο, θα μάθετε πώς λειτουργεί ο αλγόριθμος Binary Search στα παρασκήνια και πώς μπορείτε να τον εφαρμόσετε στο Python.

Συγκεκριμένα, θα μάθετε:

  • Πώς λειτουργεί ο αλγόριθμος πίσω από τα παρασκήνια για να βρει ένα στοιχείο στόχου.
  • Πώς λειτουργεί η υλοποίηση του Python γραμμή προς γραμμή.
  • Γιατί είναι ένας πολύ αποτελεσματικός αλγόριθμος σε σύγκριση με τη Γραμμική Αναζήτηση.
  • Τα πλεονεκτήματα και οι απαιτήσεις του.

Ας ξεκινήσουμε! ✨

? Εισαγωγή στη Δυαδική Αναζήτηση

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

Απαιτήσεις

Για να εφαρμόσετε τον αλγόριθμο Binary Search σε μια ακολουθία, η ακολουθία πρέπει ήδη να ταξινομηθεί με αύξουσα σειρά. Διαφορετικά, ο αλγόριθμος δεν θα βρει τη σωστή απάντηση. Εάν ναι, θα είναι από καθαρή σύμπτωση.

? Συμβουλή: Μπορείτε να ταξινομήσετε την ακολουθία πριν εφαρμόσετε τη Δυαδική Αναζήτηση με έναν αλγόριθμο ταξινόμησης που ικανοποιεί τις ανάγκες σας.

Είσοδος και έξοδος

Ο αλγόριθμος (που εφαρμόζεται ως συνάρτηση) χρειάζεται αυτά τα δεδομένα:

  • Μια ταξινομημένη ακολουθία στοιχείων (για παράδειγμα: λίστα, tuple, string).
  • Το στοιχείο στόχος που αναζητούμε.

Επιστρέφει το ευρετήριο του στοιχείου που αναζητάτε εάν βρεθεί. Εάν το στοιχείο δεν βρεθεί, επιστρέφεται το -1.

Αποδοτικότητα

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

Ας αρχίσουμε να βρούμε αυτόν τον αλγόριθμο.

? Visual Walkthrough

Θα εφαρμόσουμε τον αλγόριθμο Binary Search σε αυτήν τη λίστα:

? Συμβουλή: Παρατηρήστε ότι η λίστα είναι ήδη ταξινομημένη. Περιέλαβε τους δείκτες ως οπτική αναφορά.

Στόχος

Θέλουμε να βρούμε το ευρετήριο του ακέραιου 67 .

Διάστημα

Ας προσποιηθούμε ότι είμαστε ο αλγόριθμος. Πώς ξεκινάμε τη διαδικασία;

Ξεκινάμε επιλέγοντας τα δύο όρια του διαστήματος όπου θέλουμε να αναζητήσουμε. Θέλουμε να αναζητήσουμε ολόκληρη τη λίστα, οπότε επιλέγουμε το ευρετήριο 0ως το κάτω όριο και το ευρετήριο 5ως το ανώτερο όριο:

Μεσαίο στοιχείο

Τώρα πρέπει να βρούμε το ευρετήριο του μεσαίου στοιχείου σε αυτό το διάστημα. Αυτό το κάνουμε προσθέτοντας το κάτω όριο και το άνω όριο και διαιρώντας το αποτέλεσμα με 2 χρησιμοποιώντας ακέραια διαίρεση.

Σε αυτήν την περίπτωση, (0 + 5)//2είναι 2επειδή το αποτέλεσμα 5/2είναι 2.5και ακέραιος διαχωρισμός κόβει το δεκαδικό μέρος.

Έτσι, το μεσαίο στοιχείο βρίσκεται στο ευρετήριο 2 και το μεσαίο στοιχείο είναι ο αριθμός 6 :

Συγκρίσεις

Τώρα πρέπει να ξεκινήσουμε τη σύγκριση του μεσαίου στοιχείου με το στοιχείο στόχου μας για να δούμε τι πρέπει να κάνουμε στη συνέχεια.

Ρωτάμε:

Είναι το μεσαίο στοιχείο ίσο με το στοιχείο που αναζητούμε;

6 == 67 # False

Όχι, δεν είναι.

Έτσι ρωτάμε:

Είναι το μεσαίο στοιχείο μεγαλύτερο από το στοιχείο που αναζητούμε;

6 > 67 # False

Όχι, δεν είναι.

Έτσι, το μεσαίο στοιχείο είναι μικρότερο από το στοιχείο που αναζητούμε.

6 < 67 # True

Απόρριψη στοιχείων

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

Ξεκινήστε ξανά - Επιλέξτε τα Όρια

Τι κανουμε μετα? Έχουμε απορρίψει τα στοιχεία και ο κύκλος επαναλαμβάνεται ξανά.

Πρέπει να επιλέξουμε τα όρια για το νέο διάστημα (βλ. Παρακάτω). Αλλά προσέξτε ότι το άνω όριο διατηρείται ανέπαφο και μόνο το κάτω όριο αλλάζει.

Αυτό συμβαίνει επειδή το στοιχείο που ψάχνουμε θα μπορούσε να βρίσκεται στο πάνω μισό της λίστας. Το άνω όριο διατηρείται ανέπαφο και το κατώτερο όριο αλλάζει σε "συρρίκνωση" του διαστήματος σε ένα διάστημα όπου θα μπορούσε να βρεθεί το στοιχείο στόχος μας.

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

Μεσαίο στοιχείο

Τώρα πρέπει να βρούμε τον δείκτη του μεσαίου στοιχείου προσθέτοντας το κάτω όριο στο άνω όριο και διαιρώντας το αποτέλεσμα με 2 χρησιμοποιώντας ακέραιο διαίρεση.

Το αποτέλεσμα (3+5)//2είναι 4, έτσι το μεσαίο στοιχείο βρίσκεται στο ευρετήριο4 και το μεσαίο στοιχείο είναι 67 .

Συγκρίσεις

Ρωτάμε:

Είναι το μεσαίο στοιχείο ίσο με το στοιχείο που αναζητούμε;

67 == 67 # True

Ναι είναι! Βρήκαμε λοιπόν το στοιχείο στο ευρετήριο 4 . Η τιμή 4 επιστρέφεται και ο αλγόριθμος ολοκληρώθηκε με επιτυχία.

? Συμβουλή: Εάν το στοιχείο δεν είχε βρεθεί, η διαδικασία θα συνεχιζόταν έως ότου το διάστημα δεν ήταν πλέον έγκυρο. Εάν το στοιχείο δεν είχε βρεθεί σε ολόκληρη τη λίστα, το -1 θα είχε επιστραφεί.

? Κωδικός Walkthrough

Τώρα που έχετε μια οπτική διαίσθηση για το πώς λειτουργεί ο αλγόριθμος πίσω από τα παρασκήνια, ας ρίξουμε μια βουτιά στην επαναληπτική εφαρμογή Python αναλύοντας τον κάθε γραμμή:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

Επί κεφαλής

Εδώ έχουμε την κεφαλίδα της λειτουργίας:

def binary_search(data, elem):

Χρειάζονται δύο επιχειρήματα:

  • Η ταξινομημένη ακολουθία στοιχείων (για παράδειγμα: λίστα, πλειάδα ή συμβολοσειρά).
  • Το στοιχείο που θέλουμε να βρούμε.

Αρχικό διάστημα

Η επόμενη γραμμή ορίζει τα αρχικά κατώτερα και ανώτερα όρια:

low = 0 high = len(data) - 1

Το αρχικό κάτω όριο είναι δείκτης 0και το αρχικό άνω όριο είναι ο τελευταίος δείκτης της ακολουθίας.

Βρόχος

Θα επαναλάβουμε τη διαδικασία ενώ υπάρχει ένα έγκυρο διάστημα, ενώ το κάτω όριο είναι μικρότερο ή ίσο με το ανώτερο όριο.

while low <= high:

? Συμβουλή: Να θυμάστε ότι τα όρια είναι δείκτες.

Μεσαίο στοιχείο

Σε κάθε επανάληψη, πρέπει να βρούμε τον δείκτη του μεσαίου στοιχείου. Για να γίνει αυτό, προσθέτουμε τα κατώτερα και ανώτερα όρια και διαιρούμε το αποτέλεσμα με 2 χρησιμοποιώντας ακέραια διαίρεση.

middle = (low + high)//2

? Συμβουλή: Χρησιμοποιούμε ακέραιο διαχωρισμό σε περίπτωση που η λίστα ή το διάστημα περιέχει έναν ομοιόμορφο αριθμό στοιχείων. Για παράδειγμα, εάν η λίστα είχε 6 στοιχεία και δεν χρησιμοποιήσαμε ακέραια διαίρεση, middleθα ήταν το αποτέλεσμα του (0 + 5)/2οποίου είναι 2.5. Ένα ευρετήριο δεν μπορεί να είναι float, συνεπώς περικόψουμε το δεκαδικό τμήμα χρησιμοποιώντας //και επιλέγουμε το στοιχείο στο ευρετήριο 2.

Συγκρίσεις

Με αυτούς τους όρους (βλ. Παρακάτω), καθορίζουμε τι πρέπει να κάνουμε ανάλογα με την τιμή του μεσαίου στοιχείου data[middle]. Το συγκρίνουμε με το στοιχείο στόχου που αναζητούμε.

if data[middle] == elem: return middle elif data[middle] > elem: high = middle - 1 else: low = middle + 1

Υπάρχουν τρεις επιλογές:

  • Εάν το μεσαίο στοιχείο είναι ίσο με το στοιχείο που αναζητούμε, επιστρέφουμε αμέσως το ευρετήριο επειδή βρήκαμε το στοιχείο.
if data[middle] == elem: return middle
  • Εάν το μεσαίο στοιχείο είναι μεγαλύτερο από το στοιχείο που αναζητούμε, εκχωρούμε εκ νέου το ανώτερο όριο επειδή γνωρίζουμε ότι το στοιχείο στόχου βρίσκεται στο κάτω μισό της λίστας.
elif data[middle] > elem: high = middle - 1
  • Αλλιώς, η μόνη επιλογή που απομένει είναι ότι το μεσαίο στοιχείο είναι μικρότερο από το στοιχείο που ψάχνουμε, οπότε ξαναχωρούμε το κατώτερο όριο επειδή γνωρίζουμε ότι το στοιχείο στόχος βρίσκεται στο πάνω μισό της λίστας.
else: low = middle + 1

Το στοιχείο δεν βρέθηκε

Εάν ο βρόχος έχει ολοκληρωθεί χωρίς να βρεθεί το στοιχείο, επιστρέφεται η τιμή -1.

return -1

και έχουμε την τελική εφαρμογή του αλγορίθμου Binary Search:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

? Ειδικές περιπτώσεις

Αυτές είναι μερικές συγκεκριμένες περιπτώσεις που μπορεί να βρείτε καθώς αρχίζετε να εργάζεστε με αυτόν τον αλγόριθμο:

Επαναλαμβανόμενα στοιχεία

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

>>> >>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 7) 4 

Το στοιχείο δεν βρέθηκε

Εάν το στοιχείο δεν βρεθεί, επιστρέφεται το -1.

>>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 8) -1

Κενή ακολουθία

Εάν η ακολουθία είναι κενή, το -1 θα επιστραφεί.

>>> b = [] >>> binary_search(b, 8) -1

Μη ταξινομημένη ακολουθία

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

Αυτό το παράδειγμα επιστρέφει το σωστό αποτέλεσμα:

>>> b = [5, 7, 3, 0, -9, 2, 6] >>> binary_search(b, 6) 6

Αλλά αυτό δεν:

>>> b = [5, 7, 3, 0, -9, 2, 10, 6] >>> binary_search(b, 6) -1

? Συμβουλή: Σκεφτείτε γιατί το πρώτο παράδειγμα επιστρέφει το σωστό αποτέλεσμα. Συμβουλή: Είναι καθαρή σύμπτωση ότι η σειρά των στοιχείων συμβαίνει να κάνει τον αλγόριθμο να φτάσει στο σωστό ευρετήριο, αλλά η διαδικασία βήμα προς βήμα αξιολογεί 0, τότε 2και τελικά 6. Σε αυτήν τη συγκεκριμένη περίπτωση, για αυτό το συγκεκριμένο στοιχείο, ο σωστός δείκτης βρίσκεται ακόμη και αν η ακολουθία δεν έχει ταξινομηθεί.

More Ένα πιο σύνθετο παράδειγμα

Τώρα που είστε πιο εξοικειωμένοι με τον αλγόριθμο και την εφαρμογή του Python, εδώ έχουμε ένα πιο περίπλοκο παράδειγμα:

Θέλουμε να βρούμε το ευρετήριο του στοιχείου 45 σε αυτήν τη λίστα χρησιμοποιώντας τη Δυαδική Αναζήτηση:

Πρώτη επανάληψη

Επιλέγονται τα κάτω και τα ανώτερα όρια:

Το μεσαίο στοιχείο ( 26 ) επιλέγεται:

Αλλά το μεσαίο στοιχείο ( 26 ) δεν είναι το στοιχείο που αναζητούμε, είναι μικρότερο από 45 :

Δεύτερη επανάληψη

Έτσι μπορούμε να απορρίψουμε όλα τα στοιχεία που είναι μικρότερα από το μεσαίο στοιχείο και να επιλέξουμε νέα όρια. Το νέο κάτω όριο ( 27 ) είναι το στοιχείο που βρίσκεται ακριβώς στα δεξιά του προηγούμενου μεσαίου στοιχείου:

? Συμβουλή: Να θυμάστε ότι η λίστα είναι ήδη ταξινομημένη.

Το νέο μεσαίο στοιχείο ( 30 ) επιλέγεται:

Το μεσαίο στοιχείο ( 30 ) δεν είναι το στοιχείο που ψάχνουμε, είναι μικρότερο από 45 :

Τρίτη επανάληψη

Μπορούμε να απορρίψουμε τα στοιχεία που είναι μικρότερα ή ίσα με 30 που δεν έχουν ήδη απορριφθεί. Το κάτω όριο ενημερώνεται σε 32 :

Εδώ έχουμε μια ενδιαφέρουσα περίπτωση: το μεσαίο στοιχείο είναι ένα από τα όρια του τρέχοντος διαστήματος επειδή (7+8)//2είναι 7.

Το μεσαίο στοιχείο ( 32 ) δεν είναι το στοιχείο που αναζητούμε ( 45 ), είναι μικρότερο.

Τέταρτη επανάληψη

Μπορούμε να απορρίψουμε τα στοιχεία που είναι μικρότερα ή ίσα με 32 που δεν έχουν ήδη απορριφθεί.

Εδώ έχουμε μια άλλη πολύ ενδιαφέρουσα περίπτωση: το διάστημα έχει μόνο ένα στοιχείο.

? Συμβουλή: Αυτό το διάστημα είναι έγκυρο επειδή γράψαμε αυτήν την συνθήκη while high <= low:, η οποία περιλαμβάνει διαστήματα όπου ο δείκτης του κατώτερου ορίου είναι ίσος με τον δείκτη του άνω ορίου.

Το μεσαίο στοιχείο είναι το μόνο στοιχείο στο διάστημα επειδή (8+8)//2είναι 8, έτσι ο δείκτης του μεσαίου στοιχείου είναι 8 και το μεσαίο στοιχείο είναι 45 .

Τώρα το μεσαίο στοιχείο είναι το στοιχείο που αναζητούμε, 45 :

Έτσι επιστρέφεται η τιμή 8 (ο δείκτης):

>>> binary_search([1, 3, 7, 15, 26, 27, 30, 32, 45], 45) 8

? Επιπλέον πρακτική

Εάν θέλετε να κάνετε κάποια επιπλέον πρακτική με αυτόν τον αλγόριθμο, προσπαθήστε να εξηγήσετε πώς λειτουργεί ο αλγόριθμος πίσω από τα παρασκήνια όταν εφαρμόζεται σε αυτήν τη λίστα για να βρείτε τον ακέραιο αριθμό 90 :

[5, 8, 15, 26, 38, 56]
  • Τι συμβαίνει βήμα προς βήμα;
  • Ποια τιμή επιστρέφεται;
  • Βρέθηκε το στοιχείο;

Ελπίζω πραγματικά ότι σας άρεσε το άρθρο μου και το βρήκα χρήσιμο. Τώρα μπορείτε να εφαρμόσετε τον αλγόριθμο Binary Search στο Python. Δείτε το διαδικτυακό μου μάθημα "Αλγόριθμοι αναζήτησης και ταξινόμησης Python: Μια πρακτική προσέγγιση". Ακολούθησέ με στο τουίτερ. ⭐️