Εισαγωγή
Έχεις πέσει πάνω σε μια ομάδα μαθηματικών που είναι και τραγουδοποιοί.
Έχουν γράψει ένα τραγούδι για κάθε έναν από τους αγαπημένους τους αριθμούς και, όπως μπορείς να φανταστείς, έχουν πάρα πολλούς αγαπημένους αριθμούς (όπως το 0 ή το 73 ή το 6174).
Θέλεις πολύ να ακούσεις το τραγούδι για τον δικό σου αγαπημένο αριθμό, αλλά με τόσα τραγούδια να ψάξεις, μπορεί να σου πάρει ώρα να βρεις το σωστό.
Ευτυχώς, έχουν οργανώσει τα τραγούδια τους σε μια λίστα αναπαραγωγής ταξινομημένη κατά τίτλο, ο οποίος είναι απλώς ο αριθμός για τον οποίο μιλάει το τραγούδι.
Συνειδητοποιείς ότι μπορείς να χρησιμοποιήσεις έναν αλγόριθμο δυαδικής αναζήτησης για να βρεις γρήγορα ένα τραγούδι με βάση τον τίτλο.
Οδηγίες
Το καθήκον σου είναι να υλοποιήσεις έναν αλγόριθμο δυαδικής αναζήτησης.
Ένας αλγόριθμος δυαδικής αναζήτησης βρίσκει ένα στοιχείο σε μια λίστα χωρίζοντάς την επανειλημμένα στη μέση και κρατώντας μόνο το μισό που περιέχει το στοιχείο που ψάχνουμε.
Μας επιτρέπει να περιορίσουμε γρήγορα τις πιθανές θέσεις του στοιχείου μας μέχρι να το βρούμε ή μέχρι να έχουμε εξαλείψει όλες τις πιθανές θέσεις.
Η δυαδική αναζήτηση λειτουργεί μόνο όταν μια λίστα έχει ταξινομηθεί.
Ο αλγόριθμος έχει ως εξής:
- Βρες το μεσαίο στοιχείο μιας ταξινομημένης λίστας και σύγκρινέ το με το στοιχείο που ψάχνουμε.
- Αν το μεσαίο στοιχείο είναι το στοιχείο μας, τότε τελειώσαμε!
- Αν το μεσαίο στοιχείο είναι μεγαλύτερο από το στοιχείο μας, μπορούμε να εξαλείψουμε αυτό το στοιχείο και όλα τα στοιχεία μετά από αυτό.
- Αν το μεσαίο στοιχείο είναι μικρότερο από το στοιχείο μας, μπορούμε να εξαλείψουμε αυτό το στοιχείο και όλα τα στοιχεία πριν από αυτό.
- Αν όλα τα στοιχεία της λίστας έχουν εξαλειφθεί, τότε το στοιχείο δεν βρίσκεται στη λίστα.
- Διαφορετικά, επανάλαβε τη διαδικασία στο τμήμα της λίστας που δεν έχει εξαλειφθεί.
Ας δούμε ένα παράδειγμα:
Ας πούμε ότι ψάχνουμε τον αριθμό 23 στην παρακάτω ταξινομημένη λίστα: [4, 8, 12, 16, 23, 28, 32].
- Ξεκινάμε συγκρίνοντας το 23 με το μεσαίο στοιχείο, το 16.
- Εφόσον το 23 είναι μεγαλύτερο από το 16, μπορούμε να εξαλείψουμε το αριστερό μισό της λίστας, αφήνοντάς μας με
[23, 28, 32].
- Στη συνέχεια συγκρίνουμε το 23 με το νέο μεσαίο στοιχείο, το 28.
- Εφόσον το 23 είναι μικρότερο από το 28, μπορούμε να εξαλείψουμε το δεξί μισό της λίστας:
[23].
- Βρήκαμε το στοιχείο μας.
Υποδείξεις
Η Haskell υποστηρίζει πολλούς τύπους πινάκων. Αυτή η άσκηση χρησιμοποιεί αμετάβλητους, boxed, μη αυστηρούς πίνακες από το Data.Array. Μπορείς να διαβάσεις περισσότερα για τη χρήση αυτών των πινάκων στα παρακάτω:
Ως προαιρετική επέκταση αυτής της άσκησης, προσπάθησε να κάνεις τη συνάρτηση find να λειτουργεί για πίνακες με αυθαίρετα όρια, π.χ. πίνακες των οποίων η πρώτη θέση δεν είναι απαραίτητα 0.
