[Παίζει μουσική] 

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

Έτσι ποια είναι η ιδέα εδώ; είναι διαίρει και βασίλευε. Θέλουμε να μειώσουμε το μέγεθος του Η περιοχή αναζήτησης κατά το ήμισυ κάθε χρόνο Για να βρείτε έναν αριθμό-στόχο. Αυτό είναι όπου η κατάσταση μπαίνει στο παιχνίδι, όμως. Μπορούμε να αξιοποιήσει μόνο τη δύναμη της εξαλείφοντας ένα δεύτερο από τα στοιχεία χωρίς καν να κοιτάζει τους αν η συστοιχία έχει διευθετηθεί. 

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

Έτσι ποια είναι η ψευδοκώδικα βήματα για την δυαδική αναζήτηση; Επαναλαμβάνουμε τη διαδικασία μέχρι το συστοιχία ή, καθώς προχωράμε μέσα, υπο συστοιχίες, μικρότερα κομμάτια η αρχική διάταξη, είναι μεγέθους 0. Υπολογίστε το μέσο της τρέχουσας υπο-συστοιχία. 

Αν η τιμή που ψάχνετε είναι στο εν λόγω στοιχείο του πίνακα, να σταματήσει. Το βρηκες. Αυτό είναι υπέροχο. Διαφορετικά, αν ο στόχος είναι λιγότερο από ό, τι είναι στη μέση, Έτσι, αν η τιμή που ψάχνουμε είναι χαμηλότερο από αυτό που βλέπουμε, επαναλάβετε αυτή τη διαδικασία και πάλι, αλλά αλλάξετε το τελικό σημείο, αντί να είναι η αρχική ολοκληρώσει την πλήρη σειρά, να είναι μόνο προς τα αριστερά όπου εμείς απλά κοίταξε. 

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

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

Έτσι, μπορούμε να αρχίσουμε, έτσι δεν είναι; Λοιπόν, δεν είναι αρκετά. Θυμηθείτε τι είπα σχετικά με δυαδική αναζήτηση; Εμείς δεν μπορούμε να το κάνουμε σε ένα αδιαχώριστα συστοιχία ή αλλιώς, Δεν εγγυόμαστε ότι η ορισμένα στοιχεία ή αξίες δεν είναι είναι λάθος απορρίπτεται όταν εμείς απλά αποφασίσει να αγνοήσει ένα δεύτερο της συστοιχίας. 

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

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

Έτσι υπολογίζουμε το μέσο κατά προσθέτοντας 0 συν 14 διαιρείται δια 2? αρκετά απλή μέσο. Και μπορούμε να πούμε ότι το κεντρικό σημείο είναι τώρα 7. Έτσι είναι 15 αυτό που ψάχνετε; Όχι δεν είναι. Ψάχνουμε για 19. Αλλά γνωρίζουμε ότι το 19 είναι μεγαλύτερο από ό, τι βρήκαμε στη μέση. 

Έτσι, αυτό που μπορούμε να κάνουμε είναι αλλάξετε το σημείο εκκίνησης να είναι ακριβώς στα δεξιά του μέσο, ​​και επαναλάβετε τη διαδικασία. Και όταν το κάνουμε αυτό, λέμε τώρα η νέο σημείο εκκίνησης είναι η θέση πίνακα 8. Αυτό που κάναμε είναι αποτελεσματικά αγνοείται πάντα στα αριστερά του 15. Έχουμε εξαλειφθεί το ήμισυ του προβλήματος, και τώρα, αντί να χρειάζεται να αναζητήσετε πάνω από 15 στοιχεία σε σειρά μας, δεν έχουμε παρά να αναζητήσετε πάνω από 7. Έτσι 8 είναι το νέο σημείο εκκίνησης. 14 εξακολουθεί να είναι το τελικό σημείο. 

Και τώρα, θα πάει πάνω από αυτό και πάλι. Υπολογίζουμε το νέο μέσο. 8 συν 14 είναι 22, διαιρείται δια 2 είναι 11. Είναι αυτό που ψάχνετε; Όχι δεν είναι. Ψάχνουμε για μια τιμή που είναι λιγότερο από αυτό που μόλις βρήκα. Έτσι θα πάμε να επαναλάβουμε η διαδικασία και πάλι. Εμείς πάμε για να αλλάξετε το τελικό σημείο για να είναι ακριβώς στα αριστερά του κέντρου. Έτσι, το νέο τελικό σημείο γίνεται 10. Και τώρα, αυτό είναι το μόνο μέρος του η διάταξη θα πρέπει να ταξινομήσετε μέσω. Έτσι έχουμε πλέον εξαλειφθεί 12 από τα 15 στοιχεία. Ξέρουμε ότι αν 19 υπάρχει στη συστοιχία, το πρέπει να υπάρχει κάπου μεταξύ του στοιχείου αριθμός 8 και το στοιχείο τον αριθμό 10. 

Γι 'αυτό και υπολογίζει ξανά το νέο μέσο. 8 συν 10 είναι 18, διαιρείται με 2 9. Και σε αυτή την περίπτωση, κοιτάξτε, η στόχος είναι στη μέση. Βρήκαμε αυτό ακριβώς που ψάχνετε. Μπορούμε να σταματήσουμε. Έχουμε ολοκληρώσει επιτυχώς μια δυαδική αναζήτηση. Εντάξει. Γνωρίζουμε, λοιπόν, αυτόν τον αλγόριθμο λειτουργεί αν ο στόχος είναι κάπου μέσα της συστοιχίας. Μήπως αυτό το έργο, αν ο αλγόριθμος ο στόχος δεν είναι στη συστοιχία; Λοιπόν, ας αρχίσει πάλι, και αυτή τη φορά, ας ρίξουμε μια ματιά για το στοιχείο 16, το οποίο οπτικά μπορούμε να δούμε δεν υπάρχει πουθενά στη συστοιχία. 

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

Ποιο είναι λοιπόν το πρώτο βήμα; Υπολογίστε το μέσο της τρέχουσας σειράς. Ποιο είναι το μέσο του ισχύοντος πίνακα; Λοιπόν, αυτό είναι 7, έτσι δεν είναι; 14 συν 0 διαιρείται με 2 είναι 7. Είναι 15 αυτό που ψάχνετε; Κανένα. Είναι αρκετά κοντά, αλλά ψάχνουμε για μια τιμή λίγο μεγαλύτερη από εκείνη. 

Έτσι, γνωρίζουμε ότι πρόκειται να είναι πουθενά στα αριστερά του 15. Ο στόχος είναι μεγαλύτερη από τι είναι στο μέσον. Και έτσι θέσαμε το νέο σημείο εκκίνησης για την να είναι ακριβώς στα δεξιά της μεσαίας. Το μέσον είναι σήμερα 7, έτσι ας πούμε το νέο σημείο εκκίνησης είναι 8. Και τι έχουμε πραγματικά γίνεται και πάλι αγνοείται ολόκληρο το αριστερό μισό της συστοιχίας. 

Τώρα, επαναλαμβάνουμε το επεξεργάζονται ακόμα μία φορά. Υπολογίστε το νέο μέσο. 8 συν 14 είναι 22, διαιρείται δια 2 είναι 11. Είναι 23 αυτό που ψάχνετε; Δυστηχώς ΟΧΙ. Ψάχνουμε για μια τιμή ότι είναι μικρότερη από 23. Και στην προκειμένη περίπτωση, θα πάμε για να αλλάξετε το τελικό σημείο για να είναι ακριβώς στα αριστερά του τρέχοντος μέσο. Η τρέχουσα μέσον είναι 11, και έτσι θα θέσει το νέο τελικό σημείο για την επόμενη φορά που θα πάμε μέσω αυτής της διαδικασίας για 10. 

Και πάλι, θα περάσουν από τη διαδικασία πάλι. Υπολογίστε το μέσο. 8 συν 10 διαιρείται δια 2 είναι 9. Είναι 19 αυτό που ψάχνετε; Δυστηχώς ΟΧΙ. Είμαστε ακόμα ψάχνει για ένας αριθμός μικρότερος από αυτό. Έτσι θα αλλάξουν το τελικό σημείο αυτή τη φορά να είναι ακριβώς στα αριστερά του κέντρου. Η μέση τιμή είναι σήμερα 9, έτσι ώστε το τελικό σημείο θα είναι 8. Και τώρα, είμαστε ακριβώς ψάχνετε σε μια ενιαία συστοιχία στοιχείο. 

Ποιο είναι το μέσο αυτής της διάταξης; Λοιπόν, ξεκινά στις 8, το τελειώνει στις 8, το κεντρικό σημείο είναι 8. Είναι ότι αυτό που ψάχνετε; Ψάχνουμε για 17; Όχι, ψάχνουμε για 16. Έτσι, αν υπάρχει στη συστοιχία, θα πρέπει να υπάρχει κάπου στα αριστερά του όπου βρισκόμαστε τώρα. Λοιπόν, τι θα κάνουμε; Λοιπόν, θα ορίσετε το σημείο τέλους για να είναι ακριβώς στα αριστερά του τρέχοντος μέσο. Έτσι θα αλλάξουν το τελικό σημείο 7. Βλέπετε τι ακριβώς συνέβη εδώ, όμως; Αναζητήστε εδώ τώρα. 

Ξεκινήστε τώρα είναι μεγαλύτερη από ό, τι τέλος. Αποτελεσματικά, τα δύο άκρα της σειράς μας έχουν περάσει, και το σημείο έναρξης είναι Τώρα, μετά το τελικό σημείο. Λοιπόν, αυτό δεν κανένα νόημα, έτσι δεν είναι; Μέχρι τώρα, αυτό που μπορούμε να πούμε είναι ότι έχουν μια υπο-συστοιχία μεγέθους 0. Και μόλις είμαστε φτάσει σε αυτό το σημείο, μπορούμε τώρα εγγυηθεί ότι το στοιχείο 16 δεν υπάρχει στη συστοιχία, Επειδή το σημείο εκκίνησης και του τελικού σημείου έχουν διασχίσει. Και έτσι δεν είναι εκεί. Τώρα, παρατηρούμε ότι αυτό είναι ελαφρώς διαφορετικό από το σημείο έναρξης και λήξης σημείο είναι το ίδιο. Εάν ήμασταν που αναζητούν για 17, θα πρέπει ήταν στη συστοιχία, και το σημείο εκκίνησης και τελικό σημείο του εν λόγω τελευταία επανάληψη πριν διασχίσει αυτά τα σημεία, θα είχαμε βρεθεί εκεί 17. Είναι μόνο όταν διασχίζουν ότι μπορούμε εγγυάται ότι το στοιχείο δεν υπάρχουν στη συστοιχία. 

Έτσι, ας ρίξουμε μια πολύ λιγότερα βήματα από τη γραμμική αναζήτηση. Στη χειρότερη περίπτωση, θα έπρεπε να χωρίσουν μια λίστα με n στοιχεία επανειλημμένα κατά το ήμισυ για να βρουν το στόχο, είτε επειδή το στοιχείο στόχος θα είναι κάπου στην τελευταία διαίρεση, ή δεν υπάρχει καθόλου. Έτσι, στη χειρότερη περίπτωση, θα πρέπει να χωρίσουν οι array-- ξέρεις; Είσοδος φορές ν? εμείς πρέπει να κοπεί το πρόβλημα σε ένα δεύτερο ορισμένο αριθμό φορών. Αυτό πολλές φορές είναι log n. 

Ποιο είναι το καλύτερο σενάριο; Λοιπόν, η πρώτη φορά που υπολογίζει το μέσο, θα βρείτε αυτό που ψάχνετε. Σε όλες τις προηγούμενες παραδείγματα στη δυαδική αναζήτηση έχουμε μόλις περάσει πάνω, αν είχαμε ψάξει για το στοιχείο 15, θα έχουν διαπιστώσει ότι αμέσως. Αυτός ήταν στην αρχή. Αυτό ήταν το κεντρικό σημείο του Η πρώτη προσπάθεια σε ένα split ενός τμήματος σε δυαδική αναζήτηση. 

Και έτσι στη χειρότερη περίπτωση, δυαδική αναζήτηση τρέχει σε log n, η οποία είναι σημαντικά καλύτερη από τη γραμμική αναζήτηση, στη χειρότερη περίπτωση. Στην καλύτερη περίπτωση, τα δυαδικά αναζήτηση τρέχει σε ωμέγα-1. Έτσι δυαδική αναζήτηση είναι πολύ καλύτερα από ό, τι με τη γραμμική αναζήτηση, αλλά θα πρέπει να ασχοληθεί με τη διαδικασία του διαλογή σειρά σας για να μπορέσετε να αξιοποιούν τη δύναμη της δυαδικής αναζήτησης. 

Είμαι ο Νταγκ Lloyd. Αυτό είναι το CS 50.