Εισαγωγή
Έχεις πέσει πάνω σε μια ομάδα μαθηματικών που είναι και τραγουδοποιοί.
Έχουν γράψει ένα τραγούδι για κάθε έναν από τους αγαπημένους τους αριθμούς και, όπως μπορείς να φανταστείς, έχουν πάρα πολλούς αγαπημένους αριθμούς (όπως το 0 ή το 73 ή το 6174).
Θέλεις πολύ να ακούσεις το τραγούδι για τον δικό σου αγαπημένο αριθμό, αλλά με τόσα τραγούδια να ψάξεις, μπορεί να σου πάρει ώρα να βρεις το σωστό.
Ευτυχώς, έχουν οργανώσει τα τραγούδια τους σε μια λίστα αναπαραγωγής ταξινομημένη κατά τίτλο, ο οποίος είναι απλώς ο αριθμός για τον οποίο μιλάει το τραγούδι.
Συνειδητοποιείς ότι μπορείς να χρησιμοποιήσεις έναν αλγόριθμο δυαδικής αναζήτησης για να βρεις γρήγορα ένα τραγούδι με βάση τον τίτλο.
Οδηγίες
Το καθήκον σου είναι να υλοποιήσεις έναν αλγόριθμο δυαδικής αναζήτησης.
Ένας αλγόριθμος δυαδικής αναζήτησης βρίσκει ένα στοιχείο σε μια λίστα χωρίζοντάς την επανειλημμένα στη μέση και κρατώντας μόνο το μισό που περιέχει το στοιχείο που ψάχνουμε.
Μας επιτρέπει να περιορίσουμε γρήγορα τις πιθανές θέσεις του στοιχείου μας μέχρι να το βρούμε ή μέχρι να έχουμε εξαλείψει όλες τις πιθανές θέσεις.
Η δυαδική αναζήτηση λειτουργεί μόνο όταν μια λίστα έχει ταξινομηθεί.
Ο αλγόριθμος έχει ως εξής:
- Βρες το μεσαίο στοιχείο μιας ταξινομημένης λίστας και σύγκρινέ το με το στοιχείο που ψάχνουμε.
- Αν το μεσαίο στοιχείο είναι το στοιχείο μας, τότε τελειώσαμε!
- Αν το μεσαίο στοιχείο είναι μεγαλύτερο από το στοιχείο μας, μπορούμε να εξαλείψουμε αυτό το στοιχείο και όλα τα στοιχεία μετά από αυτό.
- Αν το μεσαίο στοιχείο είναι μικρότερο από το στοιχείο μας, μπορούμε να εξαλείψουμε αυτό το στοιχείο και όλα τα στοιχεία πριν από αυτό.
- Αν όλα τα στοιχεία της λίστας έχουν εξαλειφθεί, τότε το στοιχείο δεν βρίσκεται στη λίστα.
- Διαφορετικά, επανάλαβε τη διαδικασία στο τμήμα της λίστας που δεν έχει εξαλειφθεί.
Ας δούμε ένα παράδειγμα:
Ας πούμε ότι ψάχνουμε τον αριθμό 23 στην παρακάτω ταξινομημένη λίστα: [4, 8, 12, 16, 23, 28, 32].
- Ξεκινάμε συγκρίνοντας το 23 με το μεσαίο στοιχείο, το 16.
- Εφόσον το 23 είναι μεγαλύτερο από το 16, μπορούμε να εξαλείψουμε το αριστερό μισό της λίστας, αφήνοντάς μας με
[23, 28, 32].
- Στη συνέχεια συγκρίνουμε το 23 με το νέο μεσαίο στοιχείο, το 28.
- Εφόσον το 23 είναι μικρότερο από το 28, μπορούμε να εξαλείψουμε το δεξί μισό της λίστας:
[23].
- Βρήκαμε το στοιχείο μας.
Μηνύματα εξαιρέσεων
Κάποιες φορές είναι απαραίτητο να πετάξεις μια εξαίρεση. Όταν το κάνεις αυτό, θα πρέπει πάντα να συμπεριλαμβάνεις ένα κατατοπιστικό μήνυμα σφάλματος που να δείχνει ποια είναι η πηγή του σφάλματος. Αυτό κάνει τον κώδικά σου πιο ευανάγνωστο και βοηθάει σημαντικά στην αποσφαλμάτωση. Σε περιπτώσεις που ξέρεις ότι η πηγή του σφάλματος θα είναι συγκεκριμένου τύπου, μπορείς να επιλέξεις να κάνεις raise έναν από τους ενσωματωμένους τύπους σφαλμάτων, αλλά θα πρέπει και πάλι να συμπεριλάβεις ένα κατατοπιστικό μήνυμα.
Αυτή η άσκηση απαιτεί να χρησιμοποιήσεις την εντολή raise για να "πετάξεις" ένα ValueError όταν η τιμή που δίνεται δεν βρίσκεται μέσα στον πίνακα. Τα τεστ θα περάσουν μόνο αν και κάνεις raise την exception και συμπεριλάβεις ένα μήνυμα μαζί της.
Για να κάνεις raise ένα ValueError με μήνυμα, γράψε το μήνυμα ως όρισμα στον τύπο exception:
# example when value is not found in the array.
raise ValueError("value not in array")
