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

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

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

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

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

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

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

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

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

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