Αναζήτηση και ταξινόμηση
Η σειριακή αναζήτηση και οι παραλλαγές της, πότε αξίζει να ταξινομήσεις, και το «διαίρει και βασίλευε».
40 λεπτά
Στο σχολικό βιβλίο: Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον Γ΄ Λυκείου, 2 ενότητες
Στις Πανελλήνιες2026 Δ ·2025 επαν. Δ ·2025 Α ·2024 Δ ·2022 επαν. Α ·2022 Α ·2021 επαν. Β ·2020 επαν. Α ·2020 Α
Θα μάθεις να
- Να γράφεις τη σειριακή αναζήτηση και τις παραλλαγές της: πρώτη, τελευταία ή όλες οι εμφανίσεις, και πρόωρη στάση σε ταξινομημένο πίνακα.
- Να διαλέγεις ανάμεσα σε σειριακή και δυαδική αναζήτηση, με την προϋπόθεση της δεύτερης.
- Να συγκρίνεις το κόστος πολλών αναζητήσεων με και χωρίς ταξινόμηση.
- Να εξηγείς τη στρατηγική «διαίρει και βασίλευε».
Σειριακή αναζήτηση
Η πιο απλή: ελέγχεις τα στοιχεία ένα προς ένα από την αρχή, μέχρι να βρεθεί το ζητούμενο ή να τελειώσει ο πίνακας.
Η σημαία done υπάρχει για να σταματά ο βρόχος μόλις βρεθεί το στοιχείο. Χωρίς αυτήν, ο αλγόριθμος θα σάρωνε ολόκληρο τον πίνακα ακόμη κι όταν το βρήκε στην πρώτη θέση. Το position = -1 στην αρχή είναι η απάντηση «δεν βρέθηκε»: αν ο βρόχος τελειώσει χωρίς εύρημα, μένει .
Οι συγκρίσεις είναι εύκολο να μετρηθούν. Αν το ζητούμενο είναι στη θέση , γίνονται . Αν δεν υπάρχει, γίνονται , όσα και τα στοιχεία.
Τρεις παραλλαγές που ζητούνται
Όλες οι θέσεις και το πλήθος. Όταν η εκφώνηση λέει «να εμφανίσεις όλες τις θέσεις» ή «πόσες φορές υπάρχει», δεν σταματάς στο πρώτο εύρημα. Η σημαία φεύγει και ο βρόχος γίνεται ΓΙΑ, γιατί πρέπει να δεις όλα τα στοιχεία.
Η τελευταία εμφάνιση. Με τον ίδιο ΓΙΑ, κρατάς τη θέση σε μια μεταβλητή: ΑΝ A[i] = key ΤΟΤΕ θέση <- i. Κάθε νέο εύρημα σβήνει το προηγούμενο, και στο τέλος μένει το τελευταίο. Για την πρώτη εμφάνιση, η σειριακή με σημαία είναι πιο σύντομη: σταματά εκεί.
Πρόωρος τερματισμός σε ταξινομημένο πίνακα. Αν ο πίνακας είναι σε αύξουσα σειρά και φτάσεις σε στοιχείο μεγαλύτερο από το ζητούμενο, δεν έχει νόημα να συνεχίσεις: όλα τα επόμενα είναι ακόμα μεγαλύτερα.
Σειριακή ή δυαδική
Η δυαδική αναζήτηση απαιτεί ταξινομημένο πίνακα. Σε κάθε βήμα κοιτάζει το μεσαίο στοιχείο και πετά το μισό που δεν μπορεί να περιέχει το ζητούμενο. Ο κώδικάς της, με τον πίνακα τιμών των first, last και mid, είναι στην ενότητα «Δυαδική αναζήτηση βήμα βήμα».
| Σειριακή | Δυαδική | |
|---|---|---|
| Προϋπόθεση | καμία | ταξινομημένος πίνακας |
| Χειρότερη περίπτωση | συγκρίσεις | |
| Όλες οι εμφανίσεις | εύκολα, με ΓΙΑ | όχι άμεσα |
Το κόστος της ταξινόμησης
Αν ο πίνακας δεν είναι ταξινομημένος, η δυαδική έρχεται με λογαριασμό. Η ταξινόμηση φυσαλίδας κάνει πάντα
συγκρίσεις. Ο αλγόριθμός της, πέρασμα πέρασμα, είναι στην ενότητα «Ταξινόμηση φυσαλίδας βήμα βήμα».
Η απόφαση είναι λογαριασμός με δύο στήλες. Για αναζητήσεις σε πίνακα στοιχείων, στη χειρότερη περίπτωση:
- χωρίς ταξινόμηση: συγκρίσεις,
- ταξινόμηση μία φορά και δυαδική: .
Για λίγες αναζητήσεις κερδίζει η πρώτη. Για πολλές, η δεύτερη: η ταξινόμηση πληρώνεται μία φορά και αποσβένεται σε κάθε αναζήτηση που ακολουθεί.
Διαίρει και βασίλευε
Η στρατηγική πίσω από τη δυαδική αναζήτηση, σε τρία βήματα:
- Διαίρεση του προβλήματος σε μικρότερα του ίδιου τύπου.
- Κυριαρχία: λύση των μικρότερων, συνήθως αναδρομικά.
- Σύνθεση των επιμέρους λύσεων.
Η δυαδική αναζήτηση είναι η καθαρότερη περίπτωση: κάθε βήμα μισεύει το πρόβλημα, και η σύνθεση δεν χρειάζεται καθόλου, αφού η απάντηση βρίσκεται σε ένα μόνο από τα δύο μισά. Η σειριακή αναζήτηση και η φυσαλίδα δεν είναι «διαίρει και βασίλευε»: μικραίνουν το πρόβλημα κατά ένα στοιχείο τη φορά, όχι στο μισό.
Παραδείγματα
Παράδειγμα 1
Σε μη ταξινομημένο πίνακα 50 στοιχείων γίνεται σειριακή αναζήτηση με σημαία. Πόσες συγκρίσεις γίνονται αν το ζητούμενο είναι στη θέση 18, και πόσες αν δεν υπάρχει;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Στη θέση : ο βρόχος συγκρίνει τα ως και σταματά με τη σημαία. συγκρίσεις.
Αν δεν υπάρχει: συγκρίνει και τα , και ο βρόχος σταματά επειδή το
iέγινε . συγκρίσεις, η χειρότερη περίπτωση.Κατά μέσο όρο, αν το στοιχείο υπάρχει και κάθε θέση είναι εξίσου πιθανή, περίπου .
Παράδειγμα 2
Θέμα Β. Ο πίνακας Α έχει τις τιμές 5, 3, 5, 8, 5. Να γράψεις τον πίνακα τιμών του τμήματος «όλες οι εμφανίσεις» για key = 5, και τι εμφανίζεται.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Έξοδος:
Θέση 1,Θέση 3,Θέση 5και, μετά τον βρόχο,Πλήθος: 3. Η τελευταία γραμμή εμφανίζεται μία φορά, γιατί ηΓΡΑΨΕτου πλήθους είναι έξω από τον βρόχο.
Παράδειγμα 3
Δίνεται μη ταξινομημένος πίνακας 1000 ονομάτων και ζητείται μία αναζήτηση. Τι επιλέγεις;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Η δυαδική αποκλείεται στη μορφή που έχει ο πίνακας: απαιτεί ταξινόμηση.
Θα άξιζε να ταξινομήσεις πρώτα; Η φυσαλίδα θα έκανε συγκρίσεις. Η σειριακή χρειάζεται το πολύ .
Άρα σειριακή. Η ταξινόμηση θα κόστιζε σχεδόν πεντακόσιες φορές περισσότερο από την αναζήτηση που θα επιτάχυνε.
Παράδειγμα 4
Ένας μη ταξινομημένος πίνακας έχει 400 κωδικούς. Τι συμφέρει για 100 αναζητήσεις, και τι για 1000; Να συγκρίνεις τις χειρότερες περιπτώσεις.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Ταξινόμηση με φυσαλίδα: συγκρίσεις. Δυαδική: , άρα ανά αναζήτηση. Σειριακή: ανά αναζήτηση.
αναζητήσεις: σειριακή . Ταξινόμηση και δυαδική . Κερδίζει η σειριακή.
αναζητήσεις: σειριακή . Ταξινόμηση και δυαδική . Κερδίζει η ταξινόμηση. Η απάντηση εξαρτάται από το πλήθος των αναζητήσεων, και η αιτιολόγηση στις εξετάσεις είναι αυτός ο λογαριασμός.
Παράδειγμα 5
Ο πίνακας Α είναι σε αύξουσα σειρά: 3, 7, 10, 15, 22, 30, 41. Με την πρόωρη στάση, πόσες συγκρίσεις γίνονται για key = 20 και πόσες για key = 50;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Για το : τα είναι μικρότερα. Στο ισχύει και ο βρόχος σταματά με
i = 5. Πέντε συγκρίσεις. ΤοA[5]δεν είναι , άρα δεν βρέθηκε.Για το : κανένα στοιχείο δεν είναι . Ο βρόχος κάνει και τις επτά συγκρίσεις και τελειώνει με
i = 8.Εδώ φαίνεται γιατί χρειάζεται το
ΑΝ i <= n: μεi = 8δεν υπάρχειA[8]να συγκριθεί με το .
Παράδειγμα 6
Θέμα Δ. Οι πίνακες ΟΝ και ΠΟΣΟ έχουν το όνομα του πελάτη και το ποσό κάθε αγοράς ενός καταστήματος. Ένας πελάτης μπορεί να έχει πολλές αγορές. Να γράψεις τμήμα που διαβάζει ένα όνομα και εμφανίζει πόσες αγορές έκανε και το συνολικό ποσό, ή μήνυμα αν δεν υπάρχει.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Ζητούνται όλες οι εμφανίσεις, όχι η πρώτη:
ΓΙΑσε όλο τον πίνακα, με μετρητή και αθροιστή.Η αναζήτηση γίνεται στον ΟΝ, και το ποσό βγαίνει από τον παράλληλο πίνακα ΠΟΣΟ στην ίδια θέση
i.Έξοδος:
Μαρία 3 60. Για όνομα που λείπει, τοπλμένει και εμφανίζεται το μήνυμα.Το μήνυμα «δεν υπάρχει» μπαίνει μετά τον βρόχο, όχι σε
ΑΛΛΙΩΣμέσα του. Μέσα θα τυπωνόταν μία φορά για κάθε άλλο πελάτη.
Πολλαπλή επιλογή
Ασκήσεις
Τι πρέπει να ισχύει για τον πίνακα ώστε να εφαρμοστεί δυαδική αναζήτηση;
Τα κατάφερες;
- Να γράφεις τη σειριακή αναζήτηση και τις παραλλαγές της: πρώτη, τελευταία ή όλες οι εμφανίσεις, και πρόωρη στάση σε ταξινομημένο πίνακα.
- Να διαλέγεις ανάμεσα σε σειριακή και δυαδική αναζήτηση, με την προϋπόθεση της δεύτερης.
- Να συγκρίνεις το κόστος πολλών αναζητήσεων με και χωρίς ταξινόμηση.
- Να εξηγείς τη στρατηγική «διαίρει και βασίλευε».
Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.