Binary search

Δυαδική αναζήτηση-Περιγραφή

Ο αλγόριθμος εφαρμόζεται μόνο σε πίνακες που έχουν ταξινομημένα στοιχεία. Ο αλγόριθμος λειτουργεί ως εξής:

1. Βρίσκουμε το μεσαίο στοιχείο του ταξινομημένου πίνακα.

2. Εάν το προς αναζήτηση στοιχείο είναι ίσο με το μεσαίο στοιχείο, τότε σταματάμε την αναζήτηση αφού το στοιχείο βρέθηκε.

3. Εάν δε βρέθηκε, τότε ελέγχουμε αν το στοιχείο που αναζητούμε είναι μικρότερο ή μεγαλύτερο από το μεσαίο στοιχείο του πίνακα. Αν είναι μικρότερο, περιορίζουμε την αναζήτηση στο πρώτο μισό του πίνακα (με την προϋπόθεση ότι τα στοιχεία είναι διατεταγμένα κατά αύξουσα σειρά), ενώ αν είναι μεγαλύτερο περιορίζουμε την αναζήτηση στο δεύτερο μισό του πίνακα.

4. Η διαδικασία αυτή επαναλαμβάνεται για το κατάλληλο πρώτο ή δεύτερο μισό του πίνακα, μετά για το 1/4 του πίνακα κοκ. μέχρι, είτε να βρεθεί το στοιχείο, είτε να μην είναι δυνατό να χωρισθεί ο πίνακας περαιτέρω σε δύο νέα μέρη. 

Δυαδική αναζήτηση-Οπτικοποίηση

Στο διπλανό animation βλέπετε χαρακτηριστικά ην υπεροχή της δυαδικής αναζήτησης έναντι της σειριακής. Παρατηρήστε προσεκτικά την υστέρηση χρόνου της σειριακής!

Δυαδική αναζήτηση-Υπουργείο Παιδείας

Η δυαδική αναζήτηση διδάσκεται ως άσκηση και υλοποιείται με πρόγραμμα. ​Πέρα από το τμήμα δηλώσεων, το πρόγραμμα έχει επιπλέον τμήμα για το "γέμισμα" του πίνακα με στοιχεία. Υποθέτουμε ότι ο πίνακας γεμίζει με στοιχεία σε αύξουσα σειρά.

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

Έστω ένας πίνακας με 9 στοιχεία, ταξινομημένος σε αύξουσα σειρά όπως φαίνεται στη διπλανή εικόνα. Εφαρμόστε στο τετράδιό σας τη δυαδική αναζήτηση για το στοιχείο 71.

Multiple Choice

Θα βρει το 71 μετά από:

• 2 συγκρίσεις

• 3 συγκρίσεις

• 8 συγκρίσεις

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

Έστω ένας πίνακας με 9 στοιχεία, ταξινομημένος σε φθίνουσα σειρά όπως φαίνεται στη διπλανή εικόνα. Εφαρμόστε στο τετράδιό σας τη δυαδική αναζήτηση για το στοιχείο 71.

Multiple Choice

Θα βρει το 71 μετά από:

• 2 συγκρίσεις

• 3 συγκρίσεις

• 8 συγκρίσεις

Μέτρηση συγκρίσεων

Ένας μαθητής προσπαθεί να μετρήσει πόσες συγκρίσεις κάνει ο αλγόριθμος της δυαδικής αναζήτησης για να βρει ή όχι το 71, και σκέφθηκε να ορίσει έναν μετρητή c και να τον μηδενίσει στην αρχή.

Multiple Choice

Σε ποια θέση του κώδικα θα πρέπει να τοποθετήσει την εντολή καταμέτρησης των συγκρίσεων c <- c + 1 για να μετράει σωστά;

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

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

Τι λάθος γίνεται εδώ;

Ο κώδικας της επανάληψης της δυαδικής αναζήτησης εμφανίζεται ως εξής:

Multiple Choice

Αν τρέξει αυτός ο αλγόριθμος θα βγάλει:

• Βρέθηκε το στοιχείο 71

• Δεν βρέθηκε το στοιχείο 71

• Δεν θα εμφανισθεί τίποτε

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

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

Τι λάθος γίνεται εδώ;

Ο κώδικας της επανάληψης της δυαδικής αναζήτησης εμφανίζεται ως εξής:

Multiple Choice

Αν τρέξει αυτός ο αλγόριθμος θα βγάλει:

• Βρέθηκε το στοιχείο 71

• Δεν βρέθηκε το στοιχείο 71

• Δεν σταματάει η επανάληψη

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

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

Τι λάθος γίνεται εδώ;

Ο κώδικας της επανάληψης της δυαδικής αναζήτησης εμφανίζεται ως εξής:

Multiple Choice

Αν τρέξει αυτός ο αλγόριθμος θα βγάλει:

• Βρέθηκε το στοιχείο 71

• Δεν βρέθηκε το στοιχείο 71

• Δεν σταματάει η επανάληψη