Μετάβαση στο περιεχόμενο

Αναζήτηση και ταξινόμηση

Η σειριακή αναζήτηση και οι παραλλαγές της, πότε αξίζει να ταξινομήσεις, και το «διαίρει και βασίλευε».

40 λεπτά

Στο σχολικό βιβλίο: Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον Γ΄ Λυκείου, 2 ενότητες

Στις Πανελλήνιες2026 Δ ·2025 επαν. Δ ·2025 Α ·2024 Δ ·2022 επαν. Α ·2022 Α ·2021 επαν. Β ·2020 επαν. Α ·2020 Α

Θα μάθεις να

  1. Να γράφεις τη σειριακή αναζήτηση και τις παραλλαγές της: πρώτη, τελευταία ή όλες οι εμφανίσεις, και πρόωρη στάση σε ταξινομημένο πίνακα.
  2. Να διαλέγεις ανάμεσα σε σειριακή και δυαδική αναζήτηση, με την προϋπόθεση της δεύτερης.
  3. Να συγκρίνεις το κόστος πολλών αναζητήσεων με και χωρίς ταξινόμηση.
  4. Να εξηγείς τη στρατηγική «διαίρει και βασίλευε».

Σειριακή αναζήτηση

Η πιο απλή: ελέγχεις τα στοιχεία ένα προς ένα από την αρχή, μέχρι να βρεθεί το ζητούμενο ή να τελειώσει ο πίνακας.

Σειριακή αναζήτηση με σημαία

Ψάχνεις το 9 στον πίνακα 7, 3, 9, 4, 6. Πριν από κάθε βήμα πες τι θα γίνει. Πρόσεξε τη στιγμή που η σημαία done γίνεται ΑΛΗΘΗΣ: ο βρόχος σταματά εκεί, χωρίς να κοιτάξει το 4 και το 6.

  1. ΑΛΓΟΡΙΘΜΟΣ Σειριακή
  2. ΔΕΔΟΜΕΝΑ // A, n, key //
  3. τρέχουσα γραμμή: done ← ΨΕΥΔΗΣ
  4. position ← -1
  5. i ← 1
  6. ΟΣΟ i <= n ΚΑΙ done = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ
  7. ΑΝ A[i] = key ΤΟΤΕ
  8. done ← ΑΛΗΘΗΣ
  9. position ← i
  10. ΑΛΛΙΩΣ
  11. i ← i + 1
  12. ΤΕΛΟΣ_ΑΝ
  13. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  14. ΑΠΟΤΕΛΕΣΜΑΤΑ // done, position //
  15. ΤΕΛΟΣ_ΑΛΓΟΡΙΘΜΟΥ

Ξεκινάμε με A = [7, 3, 9, 4, 6], n = 5, key = 9.Γραμμή 3: τι τιμή θα πάρει το done;

Μεταβλητές

A
= [7, 3, 9, 4, 6]
n
= 5
key
= 9

Η σημαία done υπάρχει για να σταματά ο βρόχος μόλις βρεθεί το στοιχείο. Χωρίς αυτήν, ο αλγόριθμος θα σάρωνε ολόκληρο τον πίνακα ακόμη κι όταν το βρήκε στην πρώτη θέση. Το position = -1 στην αρχή είναι η απάντηση «δεν βρέθηκε»: αν ο βρόχος τελειώσει χωρίς εύρημα, μένει −1-1.

Οι συγκρίσεις είναι εύκολο να μετρηθούν. Αν το ζητούμενο είναι στη θέση kk, γίνονται kk. Αν δεν υπάρχει, γίνονται nn, όσα και τα στοιχεία.

Τρεις παραλλαγές που ζητούνται

Όλες οι θέσεις και το πλήθος. Όταν η εκφώνηση λέει «να εμφανίσεις όλες τις θέσεις» ή «πόσες φορές υπάρχει», δεν σταματάς στο πρώτο εύρημα. Η σημαία φεύγει και ο βρόχος γίνεται ΓΙΑ, γιατί πρέπει να δεις όλα τα στοιχεία.

Όλες οι εμφανίσεις του 9

Ο πίνακας είναι 4, 9, 2, 9, 7, 9. Πριν από κάθε έλεγχο της γραμμής 3 πες αν θα βγει ΑΛΗΘΗΣ.

  1. τρέχουσα γραμμή: πλήθος ← 0
  2. ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n
  3. ΑΝ A[i] = key ΤΟΤΕ
  4. ΓΡΑΨΕ 'Θέση', i
  5. πλήθος ← πλήθος + 1
  6. ΤΕΛΟΣ_ΑΝ
  7. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  8. ΓΡΑΨΕ 'Πλήθος:', πλήθος

Ξεκινάμε με A = [4, 9, 2, 9, 7, 9], n = 6, key = 9.Γραμμή 1: τι τιμή θα πάρει το πλήθος;

Μεταβλητές

A
= [4, 9, 2, 9, 7, 9]
n
= 6
key
= 9

Έξοδος

Η τελευταία εμφάνιση. Με τον ίδιο ΓΙΑ, κρατάς τη θέση σε μια μεταβλητή: ΑΝ A[i] = key ΤΟΤΕ θέση <- i. Κάθε νέο εύρημα σβήνει το προηγούμενο, και στο τέλος μένει το τελευταίο. Για την πρώτη εμφάνιση, η σειριακή με σημαία είναι πιο σύντομη: σταματά εκεί.

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

Σειριακή σε ταξινομημένο πίνακα, με πρόωρη στάση

Ψάχνεις το 15 στον πίνακα 2, 5, 9, 14, 20, 27. Πρόσεξε πού σταματά ο βρόχος: στο 20, χωρίς να κοιτάξει το 27.

  1. τρέχουσα γραμμή: i ← 1
  2. συνέχισε ← ΑΛΗΘΗΣ
  3. ΟΣΟ i <= n ΚΑΙ συνέχισε = ΑΛΗΘΗΣ ΕΠΑΝΑΛΑΒΕ
  4. ΑΝ A[i] >= key ΤΟΤΕ
  5. συνέχισε ← ΨΕΥΔΗΣ
  6. ΑΛΛΙΩΣ
  7. i ← i + 1
  8. ΤΕΛΟΣ_ΑΝ
  9. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
  10. βρέθηκε ← ΨΕΥΔΗΣ
  11. ΑΝ i <= n ΤΟΤΕ
  12. ΑΝ A[i] = key ΤΟΤΕ
  13. βρέθηκε ← ΑΛΗΘΗΣ
  14. ΤΕΛΟΣ_ΑΝ
  15. ΤΕΛΟΣ_ΑΝ
  16. ΓΡΑΨΕ βρέθηκε, i

Ξεκινάμε με A = [2, 5, 9, 14, 20, 27], n = 6, key = 15.Γραμμή 1: τι τιμή θα πάρει το i;

Μεταβλητές

A
= [2, 5, 9, 14, 20, 27]
n
= 6
key
= 15

Έξοδος

Σειριακή ή δυαδική

Η δυαδική αναζήτηση απαιτεί ταξινομημένο πίνακα. Σε κάθε βήμα κοιτάζει το μεσαίο στοιχείο και πετά το μισό που δεν μπορεί να περιέχει το ζητούμενο. Ο κώδικάς της, με τον πίνακα τιμών των first, last και mid, είναι στην ενότητα «Δυαδική αναζήτηση βήμα βήμα».

Σειριακή εναντίον δυαδικής

Ανέβασε το μέγεθος στα 1000. Η σειριακή χρειάζεται στη χειρότερη περίπτωση 1000 συγκρίσεις· η δυαδική 10. Κάθε διπλασιασμός του πίνακα κοστίζει στη δυαδική μία μόνο σύγκριση παραπάνω.

Η δυαδική προϋποθέτει ταξινομημένο πίνακα. Η σειριακή όχι — γι' αυτό δεν είναι πάντα η κακή επιλογή.

Συγκρίσεις για αυτή τη θέση

Σειριακή73

χειρότερη περίπτωση: 100

Δυαδική6

χειρότερη περίπτωση: 7

ΣειριακήΔυαδική
Προϋπόθεσηκαμίαταξινομημένος πίνακας
Χειρότερη περίπτωσηnn συγκρίσεις⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1
Όλες οι εμφανίσειςεύκολα, με ΓΙΑόχι άμεσα

Το κόστος της ταξινόμησης

Αν ο πίνακας δεν είναι ταξινομημένος, η δυαδική έρχεται με λογαριασμό. Η ταξινόμηση φυσαλίδας κάνει πάντα

n(n−1)2\frac{n(n-1)}{2}

συγκρίσεις. Ο αλγόριθμός της, πέρασμα πέρασμα, είναι στην ενότητα «Ταξινόμηση φυσαλίδας βήμα βήμα».

Η απόφαση είναι λογαριασμός με δύο στήλες. Για kk αναζητήσεις σε πίνακα nn στοιχείων, στη χειρότερη περίπτωση:

  • χωρίς ταξινόμηση: k⋅nk \cdot n συγκρίσεις,
  • ταξινόμηση μία φορά και δυαδική: n(n−1)2+k⋅(⌊log⁡2n⌋+1)\dfrac{n(n-1)}{2} + k \cdot (\lfloor \log_2 n \rfloor + 1).

Για λίγες αναζητήσεις κερδίζει η πρώτη. Για πολλές, η δεύτερη: η ταξινόμηση πληρώνεται μία φορά και αποσβένεται σε κάθε αναζήτηση που ακολουθεί.

Διαίρει και βασίλευε

Η στρατηγική πίσω από τη δυαδική αναζήτηση, σε τρία βήματα:

  1. Διαίρεση του προβλήματος σε μικρότερα του ίδιου τύπου.
  2. Κυριαρχία: λύση των μικρότερων, συνήθως αναδρομικά.
  3. Σύνθεση των επιμέρους λύσεων.

Η δυαδική αναζήτηση είναι η καθαρότερη περίπτωση: κάθε βήμα μισεύει το πρόβλημα, και η σύνθεση δεν χρειάζεται καθόλου, αφού η απάντηση βρίσκεται σε ένα μόνο από τα δύο μισά. Η σειριακή αναζήτηση και η φυσαλίδα δεν είναι «διαίρει και βασίλευε»: μικραίνουν το πρόβλημα κατά ένα στοιχείο τη φορά, όχι στο μισό.

Παραδείγματα

Παράδειγμα 1

Σε μη ταξινομημένο πίνακα 50 στοιχείων γίνεται σειριακή αναζήτηση με σημαία. Πόσες συγκρίσεις γίνονται αν το ζητούμενο είναι στη θέση 18, και πόσες αν δεν υπάρχει;

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 2

Θέμα Β. Ο πίνακας Α έχει τις τιμές 5, 3, 5, 8, 5. Να γράψεις τον πίνακα τιμών του τμήματος «όλες οι εμφανίσεις» για key = 5, και τι εμφανίζεται.

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 3

Δίνεται μη ταξινομημένος πίνακας 1000 ονομάτων και ζητείται μία αναζήτηση. Τι επιλέγεις;

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 4

Ένας μη ταξινομημένος πίνακας έχει 400 κωδικούς. Τι συμφέρει για 100 αναζητήσεις, και τι για 1000; Να συγκρίνεις τις χειρότερες περιπτώσεις.

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 5

Ο πίνακας Α είναι σε αύξουσα σειρά: 3, 7, 10, 15, 22, 30, 41. Με την πρόωρη στάση, πόσες συγκρίσεις γίνονται για key = 20 και πόσες για key = 50;

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 6

Θέμα Δ. Οι πίνακες ΟΝ και ΠΟΣΟ έχουν το όνομα του πελάτη και το ποσό κάθε αγοράς ενός καταστήματος. Ένας πελάτης μπορεί να έχει πολλές αγορές. Να γράψεις τμήμα που διαβάζει ένα όνομα και εμφανίζει πόσες αγορές έκανε και το συνολικό ποσό, ή μήνυμα αν δεν υπάρχει.

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Πολλαπλή επιλογή

Πολλαπλή επιλογήΆσκηση 1 από 10
Η δυαδική αναζήτηση προϋποθέτει ότι ο πίνακας είναι:

Ασκήσεις

ΒασικήΆσκηση 1 από 8

Τι πρέπει να ισχύει για τον πίνακα ώστε να εφαρμοστεί δυαδική αναζήτηση;

Τα κατάφερες;

  • Να γράφεις τη σειριακή αναζήτηση και τις παραλλαγές της: πρώτη, τελευταία ή όλες οι εμφανίσεις, και πρόωρη στάση σε ταξινομημένο πίνακα.
  • Να διαλέγεις ανάμεσα σε σειριακή και δυαδική αναζήτηση, με την προϋπόθεση της δεύτερης.
  • Να συγκρίνεις το κόστος πολλών αναζητήσεων με και χωρίς ταξινόμηση.
  • Να εξηγείς τη στρατηγική «διαίρει και βασίλευε».

Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.

Βρήκες κάποιο λάθος;