Η δυαδική αναζήτηση ήταν εντός ύλης όπως λέει και ο Κώστας.
Δυστυχώς βγήκε εκτός, όταν αφαιρεθηκε το ένα βιβλίο. Μάλιστα δεν βγήκε εκτός επειδή δεν έπρεπε να διδαχτεί, βγήκε εκτός γιατί από κακή επιλογή έδωσαν οι συγγραφείς τον αλγόριθμό της με αναδρομή στο σχολικό βιβλίο. Αν και στο τετράδιο του μαθητή είναι χωρίς αναδρομή, αλλά έχει κάποιο λάθος από ότι θυμάμαι.
Πάντως είναι πολύ κακό που είναι εκτός ύλης, για πολλούς λόγους που δεν είναι της παρούσης να αναπτύξουμε.
Εγώ πάντως εκτός από το ότι το σενάριο το δουλεύω και με δομές επανάληψης και παιχνίδι μεταξύ κινητού και ανθρώπου, όπου το κινητό έχει βάλει στη μνήμη έναν αριθμό απο το ένα μέχρι το 10 που πρέπει να μαντέψουμε και μας λέει κάθε φορά αν αυτός που δώσαμε είναι μικρότερος ή μεγαλύτερος άμα δεν τον έχουμε εντοπίσει, δίνω στους μαθητές την επόμενη άσκηση...
Δίνεται ο μονοδιάστατος πίνακας Π με Ν διαφορετικά ταξινομημένα κατά αύξουσα διάταξη στοιχεία. Να αναπτύξετε αλγόριθμο ο οποίος θα αναζητάει αν υπάρχει δεδομένο στοιχείο στον πίνακα. Ο αλγόριθμος θα επιστρέφει την ύπαρξη ή μη του ζητούμενου στοιχείου και τη θέση του στοιχείου αν υπάρχει.
Ο αλγόριθμος αναζήτησης να αναπτυχθεί ως εξής: έστω ότι αναζητείται το στοιχείο ζητούμενο στον πίνακα Π που περιέχει Ν ταξινομημένα στοιχεία. Το ζητούμενο είναι πιθανόν να βρίσκεται μεταξύ της πρώτης και της τελευταίας θέσης του πίνακα. Συγκρίνουμε το ζητούμενο με το περιεχόμενο της μεσαίας θέσης του πίνακα Π. Στο σημείο αυτό μπορούν να συμβούν τρία ενδεχόμενα:
• Αν το στοιχείο στη θέση αυτή είναι ίσο με το ζητούμενο τότε εντοπίστηκε το ζητούμενο στοιχείο.
• Αν το ζητούμενο είναι μικρότερο από το στοιχείο στη μεσαία θέση, τότε είναι βέβαιο ότι το στοιχείο αποκλείεται να βρίσκεται μετά τη μεσαία θέση και έτσι το διάστημα αναζήτησης περιορίζεται στο μισό του προηγούμενου προς τα πάνω.
• Αν το ζητούμενο είναι μεγαλύτερο από το στοιχείο στη μεσαία θέση, τότε είναι βέβαιο ότι το στοιχείο αποκλείεται να βρίσκεται πριν τη μεσαία θέση και έτσι το διάστημα αναζήτησης περιορίζεται στο μισό του προηγούμενου προς τα κάτω.
Η διαδικασία να επαναλαμβάνεται μέχρι να εντοπιστεί το ζητούμενο στοιχείο ή μέχρι να εξαντληθούν τα προς εξέταση διαστήματα και δεν εντοπιστεί το ζητούμενο.
Σημεώση: Ο έλεγχος αυτός μπορεί να υλοποιηθεί με τη χρήση δύο μεταβλητών που θα αποτελούν τα άκρα του εκάστοτε διαστήματος. Την πρώτη φορά οι μεταβλητές αυτές έχουν τιμή 1 και Ν αντίστοιχα, τη δεύτερη φορά, αν το στοιχείο που αναζητείται είναι μικρότερο από το στοιχείο της μεσαίας θέσης, η μεταβλητή Ν μεταβάλλεται ώστε να δείχνει μία θέση πριν τη μεσαία και έτσι το διάστημα περιορίζεται κ.ο.κ.
Η εκφώνηση μπορεί να βελτιωθεί και άλλο. Η ουσία είναι ότι έχουν τις αλγοριθμικές γνώσεις για να το αντιμετωπίσουν οι μαθητές.
Μάλιστα μετά συζητάς και άλλα ζητήματα όπως σύγκρισης της σειριακής με τη δυαδική, χειρότερη περίπτωση δυαδικής και άλλα.
Χρειάζεται χρόνος, αλλά αξίζει τον κόπο...
ΣΔ
