ROB BOWDEN: Γεια σου, είμαι Rob. Πώς μπορούμε να απασχολούν μια δυαδική αναζήτηση; Ας μάθουμε. Έτσι, σημειώστε ότι αυτή η έρευνα θα πάμε να εφαρμόσει αναδρομικά. Θα μπορούσατε επίσης να εφαρμόσουν δυαδική αναζήτηση επαναληπτικά, οπότε αν το έκανες αυτό, ότι είναι απολύτως εντάξει. 

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

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

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

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

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

Στην αναδρομική κλήση για την αναζήτηση, είμαστε Τώρα λένε ότι το μήκος του συστοιχία είναι το μεσαίο. Έτσι, εάν σειρά μας ήταν μεγέθους 20 και αναζήτηση στο δείκτη 10, δεδομένου ότι είναι μέσα 20 διαιρείται με το 2, αυτό σημαίνει ότι είμαστε περνώντας 10 ως το νέο το μήκος του πίνακα μας. Να θυμάστε ότι όταν έχετε μια σειρά μήκους 10, αυτό σημαίνει ότι η έγκυρη στοιχεία είναι σε δείκτες 0 έως 9. Έτσι, αυτό είναι ακριβώς αυτό που θέλουμε να καθορίσετε μας ενημέρωση array - το αριστερό συστοιχία από το μεσαίο στοιχείο. 

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

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

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

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

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

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

Τώρα, δεν μπορούμε δυαδική αναζήτηση πάνω μια σειρά που είναι αδιαχώριστα. Οπότε, ας πάρει αυτό διευθετηθεί. Τώρα, παρατηρούμε ότι το είδος είναι τα δύο τελευταία παράμετροι int αξιών, η οποία είναι η πίνακα που είμαστε διαλογή, και int n, το οποίο είναι το μήκος του πίνακα που είμαστε διαλογής. Έτσι, εδώ θέλουμε να εφαρμόσουμε ένας αλγόριθμος ταξινόμησης ότι είναι o κ τετράγωνο. Θα μπορούσατε να επιλέξετε bubble sort, η επιλογή είδος ή είδος εισαγωγής, ή κάποιο άλλο είδος δεν έχουμε δει στην τάξη. Αλλά εδώ, θα πάμε να χρησιμοποιήσετε είδος επιλογής. 

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

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

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

Έτσι, εδώ, τιμές j συν ένα - αυτό είναι λιγότερο από ό, τι είμαστε σήμερα λαμβάνοντας υπόψη το ελάχιστο. Στη συνέχεια, θα πάμε για να ενημερώσετε τι νομίζουμε ότι είναι το ελάχιστο για να δείκτη j συν 1. Έτσι, κάνουν ότι σε ολόκληρο το φάσμα, και μετά από αυτό για το βρόχο, το ελάχιστο θα πρέπει να είναι το ελάχιστο στοιχείο από το i-th θέση στη συστοιχία. 

Μόλις έχουμε ότι, μπορούμε να ανταλλάξουν το ελάχιστη τιμή στη θέση i-th στη συστοιχία. Έτσι, αυτό είναι απλά ένα πρότυπο ανταλλαγής. Εμείς αποθηκεύουν σε προσωρινή αξία - το i-οστό τιμή στον πίνακα - μπει στο i-οστό τιμή στον πίνακα της ελάχιστη τιμή που ανήκει εκεί, και στη συνέχεια να αποθηκεύσετε πίσω στο όταν η τρέχουσα ελάχιστη τιμή που χρησιμοποιείται για να είναι η i-th τιμή στον πίνακα, έτσι ότι δεν θα το χάσετε. 

Έτσι, αυτό συνεχίζει την επόμενη επανάληψη. Θα αρχίσει να ψάχνει για το δεύτερο ελάχιστη τιμή και τοποθετήστε το ότι σε δεύτερη θέση. Την τρίτη επανάληψη, θα αναζητήσουμε η τρίτη ελάχιστη τιμή και το ένθετο ότι στην τρίτη θέση, και έτσι στις μέχρι να έχουμε μια ταξινομημένη σειρά. Το όνομά μου είναι Rob, και αυτό Ήταν ένα είδος επιλογής.