Δυαδική Αναζήτηση

Οδηγίες

Το καθήκον σου είναι να υλοποιήσεις έναν αλγόριθμο δυαδικής αναζήτησης.

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

Ο αλγόριθμος έχει ως εξής:

• Βρες το μεσαίο στοιχείο μιας ταξινομημένης λίστας και σύγκρινέ το με το στοιχείο που ψάχνουμε.
• Αν το μεσαίο στοιχείο είναι το στοιχείο μας, τότε τελειώσαμε!
• Αν το μεσαίο στοιχείο είναι μεγαλύτερο από το στοιχείο μας, μπορούμε να εξαλείψουμε αυτό το στοιχείο και όλα τα στοιχεία μετά από αυτό.
• Αν το μεσαίο στοιχείο είναι μικρότερο από το στοιχείο μας, μπορούμε να εξαλείψουμε αυτό το στοιχείο και όλα τα στοιχεία πριν από αυτό.
• Αν όλα τα στοιχεία της λίστας έχουν εξαλειφθεί, τότε το στοιχείο δεν βρίσκεται στη λίστα.
• Διαφορετικά, επανάλαβε τη διαδικασία στο τμήμα της λίστας που δεν έχει εξαλειφθεί.

Ας δούμε ένα παράδειγμα:

Ας πούμε ότι ψάχνουμε τον αριθμό 23 στην παρακάτω ταξινομημένη λίστα: [4, 8, 12, 16, 23, 28, 32].

• Ξεκινάμε συγκρίνοντας το 23 με το μεσαίο στοιχείο, το 16.
• Εφόσον το 23 είναι μεγαλύτερο από το 16, μπορούμε να εξαλείψουμε το αριστερό μισό της λίστας, αφήνοντάς μας με [23, 28, 32].
• Στη συνέχεια συγκρίνουμε το 23 με το νέο μεσαίο στοιχείο, το 28.
• Εφόσον το 23 είναι μικρότερο από το 28, μπορούμε να εξαλείψουμε το δεξί μισό της λίστας: [23].
• Βρήκαμε το στοιχείο μας.

Συμπεριφορά

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

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

Διάβασε την τεκμηρίωση και τα παραδείγματα για τη συνάρτηση searchsorted για περισσότερες λεπτομέρειες:

searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.

See also: insorted, searchsortedfirst, sort, findall.

Examples

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0

Προαιρετικές εργασίες

• Επέκτεινε τη λύση σου ώστε να υποστηρίζει τα ορίσματα με λέξεις-κλειδιά by, lt και rev, έτσι ώστε το by να προσδιορίζει έναν μετασχηματισμό που εφαρμόζεται σε όλα τα στοιχεία της λίστας, το lt να προσδιορίζει μια σύγκριση και το rev να προσδιορίζει αν η λίστα είναι ταξινομημένη με αντίστροφη σειρά. Όταν χρησιμοποιούνται αυτές οι παράμετροι, πρέπει να υποθέσεις ότι η λίστα έχει ήδη ταξινομηθεί με αυτές τις παραμέτρους. Δες την τεκμηρίωση για τη sort για περισσότερες λεπτομέρειες.
• Υποστήριξε λίστες όπου το στοιχείο-στόχος επαναλαμβάνεται (βρες την πρώτη και την τελευταία θέση όπου το στοιχείο-στόχος συγκρίνεται ως ίσο).

---

Πηγή

Wikipedia