Εισαγωγή
Έχεις πέσει πάνω σε μια ομάδα μαθηματικών που είναι και τραγουδοποιοί.
Έχουν γράψει ένα τραγούδι για κάθε έναν από τους αγαπημένους τους αριθμούς και, όπως μπορείς να φανταστείς, έχουν πάρα πολλούς αγαπημένους αριθμούς (όπως το 0 ή το 73 ή το 6174).
Θέλεις πολύ να ακούσεις το τραγούδι για τον δικό σου αγαπημένο αριθμό, αλλά με τόσα τραγούδια να ψάξεις, μπορεί να σου πάρει ώρα να βρεις το σωστό.
Ευτυχώς, έχουν οργανώσει τα τραγούδια τους σε μια λίστα αναπαραγωγής ταξινομημένη κατά τίτλο, ο οποίος είναι απλώς ο αριθμός για τον οποίο μιλάει το τραγούδι.
Συνειδητοποιείς ότι μπορείς να χρησιμοποιήσεις έναν αλγόριθμο δυαδικής αναζήτησης για να βρεις γρήγορα ένα τραγούδι με βάση τον τίτλο.
Οδηγίες
Το καθήκον σου είναι να υλοποιήσεις έναν αλγόριθμο δυαδικής αναζήτησης.
Ένας αλγόριθμος δυαδικής αναζήτησης βρίσκει ένα στοιχείο σε μια λίστα χωρίζοντάς την επανειλημμένα στη μέση και κρατώντας μόνο το μισό που περιέχει το στοιχείο που ψάχνουμε.
Μας επιτρέπει να περιορίσουμε γρήγορα τις πιθανές θέσεις του στοιχείου μας μέχρι να το βρούμε ή μέχρι να έχουμε εξαλείψει όλες τις πιθανές θέσεις.
Η δυαδική αναζήτηση λειτουργεί μόνο όταν μια λίστα έχει ταξινομηθεί.
Ο αλγόριθμος έχει ως εξής:
- Βρες το μεσαίο στοιχείο μιας ταξινομημένης λίστας και σύγκρινέ το με το στοιχείο που ψάχνουμε.
- Αν το μεσαίο στοιχείο είναι το στοιχείο μας, τότε τελειώσαμε!
- Αν το μεσαίο στοιχείο είναι μεγαλύτερο από το στοιχείο μας, μπορούμε να εξαλείψουμε αυτό το στοιχείο και όλα τα στοιχεία μετά από αυτό.
- Αν το μεσαίο στοιχείο είναι μικρότερο από το στοιχείο μας, μπορούμε να εξαλείψουμε αυτό το στοιχείο και όλα τα στοιχεία πριν από αυτό.
- Αν όλα τα στοιχεία της λίστας έχουν εξαλειφθεί, τότε το στοιχείο δεν βρίσκεται στη λίστα.
- Διαφορετικά, επανάλαβε τη διαδικασία στο τμήμα της λίστας που δεν έχει εξαλειφθεί.
Ας δούμε ένα παράδειγμα:
Ας πούμε ότι ψάχνουμε τον αριθμό 23 στην παρακάτω ταξινομημένη λίστα: [4, 8, 12, 16, 23, 28, 32].
- Ξεκινάμε συγκρίνοντας το 23 με το μεσαίο στοιχείο, το 16.
- Εφόσον το 23 είναι μεγαλύτερο από το 16, μπορούμε να εξαλείψουμε το αριστερό μισό της λίστας, αφήνοντάς μας με
[23, 28, 32].
- Στη συνέχεια συγκρίνουμε το 23 με το νέο μεσαίο στοιχείο, το 28.
- Εφόσον το 23 είναι μικρότερο από το 28, μπορούμε να εξαλείψουμε το δεξί μισό της λίστας:
[23].
- Βρήκαμε το στοιχείο μας.
Περιορισμοί
Η Rust παρέχει στην πρότυπη βιβλιοθήκη της ήδη μια
συνάρτηση δυαδικής αναζήτησης.
Για αυτή την άσκηση δεν πρέπει να χρησιμοποιήσεις αυτή τη συνάρτηση, αλλά μόνο άλλα βασικά εργαλεία.
Για επιπλέον πόντους
Κατάφερες να περάσουν τα test και να είναι ο κώδικας καθαρός; Αν θέλεις,
υπάρχουν μερικά επιπλέον πράγματα που θα μπορούσες να δοκιμάσεις.
- Αυτή τη στιγμή η συνάρτηση find σου μάλλον θα δουλεύει μόνο για slices αριθμών,
αλλά το σύστημα τύπων της Rust είναι αρκετά ευέλικτο ώστε να φτιάξεις μια συνάρτηση find
που να δουλεύει σε όλα τα slices που περιέχουν στοιχεία τα οποία μπορούν να διαταχθούν.
- Επιπλέον, αυτή η συνάρτηση find μπορεί να δουλέψει όχι μόνο σε slices, αλλά ταυτόχρονα
και σε ένα Vec ή ένα Array.
Για να τρέξεις τα επιπλέον test, αφαίρεσε τη σημαία #[ignore] και εκτέλεσε τα test με
το feature generic, ως εξής:
$ cargo test --features generic
Έπειτα, μοιράσου τις σκέψεις σου σε ένα σχόλιο στην υποβολή σου. Έκανε αυτό
το πείραμα τον κώδικα καλύτερο; Χειρότερο; Έμαθες κάτι από αυτό;
