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

ZAMYLA CHAN: Το πρώτο πράγμα που θα μπορούσε Προκήρυξη για εύρημα είναι ότι έχουμε ήδη Οι κώδικα γραμμένο για μας. Αυτό ονομάζεται κώδικας διανομής. Έτσι, δεν είμαστε απλά γράφοντας τη δική μας κωδικοποίηση από το μηδέν πια. Αντίθετα, είμαστε συμπληρώνοντας τα κενά σε κάποια προ-υπάρχοντα κώδικα. 

Το πρόγραμμα ΡΓΝϋ.Ο ζητά για τους αριθμούς να γεμίσει το άχυρα, αναζητά η άχυρα για μια βελόνα χρήστης υπέβαλε, και το κάνει αυτό με την κλήση του είδους και αναζήτησης, τα καθήκοντα που ορίζονται σε helpers.c. Έτσι ΡΓΝϋ.Ο είναι γραμμένο ήδη. Η δουλειά σας είναι να γράψετε βοηθοί. 

Οπότε τι κάνουμε; Είμαστε εφαρμογής δύο λειτουργίες. Αναζήτηση, η οποία επιστρέφει true αν η τιμή βρίσκεται στα άχυρα, επιστρέφοντας false αν η τιμή είναι όχι στα άχυρα. Και τότε είμαστε, επίσης, την εφαρμογή της ταξινόμησης το οποίο ταξινομεί τον πίνακα που ονομάζεται αξίες. 

Έτσι, ας αντιμετωπίσουμε την αναζήτηση. Αναζήτηση εφαρμόζεται σήμερα ως γραμμική αναζήτηση, αλλά μπορείτε να το κάνετε πολύ καλύτερο από αυτό. Γραμμική αναζήτηση υλοποιείται σε O χρόνο n, η οποία είναι πολύ αργή. Αν και, να αναζητήσετε οποιαδήποτε λίστα που του έχουν ανατεθεί. Η δουλειά σου είναι να εφαρμόσει δυαδική αναζήτηση, που έχει τρέξει χρόνο O του log n. Αυτό είναι αρκετά γρήγορα. 

Αλλά υπάρχει ένας όρος. Δυαδική αναζήτηση μπορεί μόνο αναζήτηση μέσω προ-ταξινομημένο καταλόγους. Γιατί συμβαίνει αυτό; 

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

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

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

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

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

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

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

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

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

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

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

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