Καλείστε να σκεφτείτε έναν ακέραιο αριθμό μεταξύ 0 - 127. Η γάτα θα προσπαθήσει να βρει τον αριθμό με διαδοχικές δοκιμές, περιορίζοντας το εύρος τιμών σε κάθε δοκιμή στο μισό. Στην ερώτηση της γάτας καλείστε να πατήσετε το πλήκτρο n (no) στην περίπτωση που η απάντηση είναι αρνητική και το πλήκτρο y (yes) στην περίπτωση που η απάντηση είναι καταφατική.
Binary Search - Δυαδική αναζήτηση ονομάζεται ένας αναδρομικός αλγόριθμος αναζήτησης ενός στοιχείου (το λεγόμενο στοιχείο-κλειδί) σε έναν ταξινομημένο μονοδιάστατο πίνακα. Ο αλγόριθμος αυτός χρησιμοποιεί την τεχνική Διαίρει και Βασίλευε. Εν γένει, η αναζήτηση σε έναν μη ταξινομημένο πίνακα γίνεται σε χρόνο γραμμικό ως προς το μέγεθος της εισόδου, συγκρίνοντας ένα προς ένα τα στοιχεία της εισόδου με το κλειδί. Όμως, η δυαδική αναζήτηση στηρίζεται στο γεγονός ότι ο πίνακας είναι ταξινομημένος, μειώνοντας έτσι σημαντικά τον αριθμό των συγκρίσεων που απαιτούνται. Αρχικά ο αλγόριθμος θεωρεί ότι το κλειδί μπορεί να βρίσκεται οπουδήποτε μέσα στο διάνυσμα. Ξεκινά συγκρίνοντας το κλειδί με την τιμή του στοιχείου που βρίσκεται στο μέσο του διανύσματος. Αν είναι ίσα, τότε ο αλγόριθμος τερματίζει επιστρέφοντας τη θέση αυτή. Αν το κλειδί είναι μεγαλύτερο, τότε μειώνει το εύρος στο δεξί-μισό τμήμα του προηγούμενου τμήματος που εξέταζε και επαναλαμβάνει το πρώτο βήμα όχι για όλο το διάνυσμα, αλλά μόνο για το τμήμα του διανύσματος που επέλεξε. Αν το κλειδί είναι μικρότερο, τότε μειώνει το εύρος στο αριστερό-μισό τμήμα του προηγούμενου τμήματος που εξέταζε και επαναλαμβάνει το πρώτο βήμα όχι για όλο το διάνυσμα, αλλά μόνο για το τμήμα του διανύσματος που επέλεξε. Μετά από έναν πεπερασμένο αριθμό βημάτων, ο αλγόριθμος είτε θα βρει τη ζητούμενη θέση. Δείτε και: https://scratch.mit.edu/projects/334311120/
