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