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

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

Πληροφορική, Γ΄ Λυκείου. https://www.akademio.gr/el/lyk-c/informatics/searching-sorting

## Τι θα μάθεις

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

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

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

*Διαδραστικό στη σελίδα: Σειριακή αναζήτηση με σημαία*

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

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

> **Κλειδί**
>
> Η σειριακή αναζήτηση είναι η **μόνη** επιλογή σε τρεις περιπτώσεις:
>
> - ο πίνακας **δεν** είναι ταξινομημένος,
> - ο πίνακας είναι μικρός,
> - η αναζήτηση γίνεται **μία φορά**: δεν αξίζει να ταξινομήσεις για μία χρήση.
>
> Και είναι η μόνη που δουλεύει σε **σειριακά** μέσα, όπου δεν μπορείς να πας κατευθείαν στη μέση.

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

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

*Διαδραστικό στη σελίδα: Όλες οι εμφανίσεις του 9*

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

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

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

> **Πρόσεχε**
>
> **Γιατί δύο `ΑΝ` στο τέλος και όχι ένα με `ΚΑΙ`;** Αν το ζητούμενο είναι μεγαλύτερο από όλα, ο βρόχος τελειώνει με `i = n + 1`. Η συνθήκη `i <= n ΚΑΙ A[i] = key` θα ζητούσε το `A[n + 1]`, που δεν υπάρχει. Μη βασίζεσαι ότι ο δεύτερος όρος ενός `ΚΑΙ` δεν θα υπολογιστεί όταν ο πρώτος είναι ψευδής. Το εσωτερικό `ΑΝ` εκτελείται μόνο όταν η θέση υπάρχει.
>
> Για τον ίδιο λόγο ο βρόχος έχει σημαία και όχι συνθήκη `ΟΣΟ i <= n ΚΑΙ A[i] < key`.

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

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

*Διαδραστικό στη σελίδα: Σειριακή εναντίον δυαδικής*

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

> **Πρόσεχε**
>
> Η δυαδική αναζήτηση σε **μη ταξινομημένο** πίνακα δεν είναι απλώς πιο αργή: είναι **λάθος**. Θα απορρίψει το μισό του πίνακα βασισμένη σε σύγκριση που δεν σημαίνει τίποτα, και θα απαντήσει «δεν βρέθηκε» για στοιχείο που υπάρχει.

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

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

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

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

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

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

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

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

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

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

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

> **Θυμήσου**
>
> Γιατί $1000$ στοιχεία θέλουν μόλις $10$ συγκρίσεις: κάθε σύγκριση **μισεύει** το διάστημα.
>
> $$
> \begin{aligned}
> &1000 \to 500 \to 250 \to 125 \to 63 \to 32 \\
> &\to 16 \to 8 \to 4 \to 2 \to 1
> \end{aligned}
> $$
>
> Δέκα υποδιαιρέσεις, γιατί $2^{10} = 1024 > 1000$. Διπλασίασε τον πίνακα σε $2000$ και το κόστος γίνεται $11$, όχι $20$.

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

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

1. **Στη θέση $18$:** ο βρόχος συγκρίνει τα $A[1]$ ως $A[18]$ και σταματά με τη σημαία. **$18$ συγκρίσεις.**
2. **Αν δεν υπάρχει:** συγκρίνει και τα $50$, και ο βρόχος σταματά επειδή το `i` έγινε $51$. **$50$ συγκρίσεις**, η χειρότερη περίπτωση.
3. **Κατά μέσο όρο**, αν το στοιχείο υπάρχει και κάθε θέση είναι εξίσου πιθανή, περίπου $n/2 = 25$.

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

1. *Διαδραστικό στη σελίδα: Όλες οι εμφανίσεις του 5*
2. **Έξοδος:** `Θέση 1`, `Θέση 3`, `Θέση 5` και, μετά τον βρόχο, `Πλήθος: 3`. Η τελευταία γραμμή εμφανίζεται μία φορά, γιατί η `ΓΡΑΨΕ` του πλήθους είναι **έξω** από τον βρόχο.

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

1. **Η δυαδική αποκλείεται** στη μορφή που έχει ο πίνακας: απαιτεί ταξινόμηση.
2. **Θα άξιζε να ταξινομήσεις πρώτα;** Η φυσαλίδα θα έκανε $\dfrac{1000 \cdot 999}{2} = 499{.}500$ συγκρίσεις. Η σειριακή χρειάζεται το πολύ $1000$.
3. **Άρα σειριακή.** Η ταξινόμηση θα κόστιζε σχεδόν πεντακόσιες φορές περισσότερο από την αναζήτηση που θα επιτάχυνε.

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

1. **Ταξινόμηση με φυσαλίδα:** $\dfrac{400 \cdot 399}{2} = 79{.}800$ συγκρίσεις. **Δυαδική:** $2^9 = 512 > 400$, άρα $9$ ανά αναζήτηση. **Σειριακή:** $400$ ανά αναζήτηση.
2. **$100$ αναζητήσεις:** σειριακή $100 \cdot 400 = 40{.}000$. Ταξινόμηση και δυαδική $79{.}800 + 900 = 80{.}700$. **Κερδίζει η σειριακή.**
3. **$1000$ αναζητήσεις:** σειριακή $400{.}000$. Ταξινόμηση και δυαδική $79{.}800 + 9{.}000 = 88{.}800$. **Κερδίζει η ταξινόμηση.** Η απάντηση εξαρτάται από το πλήθος των αναζητήσεων, και η αιτιολόγηση στις εξετάσεις είναι αυτός ο λογαριασμός.

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

1. **Για το $20$:** τα $3, 7, 10, 15$ είναι μικρότερα. Στο $22$ ισχύει $22 \ge 20$ και ο βρόχος σταματά με `i = 5`. **Πέντε συγκρίσεις.** Το `A[5]` δεν είναι $20$, άρα δεν βρέθηκε.
2. **Για το $50$:** κανένα στοιχείο δεν είναι $\ge 50$. Ο βρόχος κάνει και τις **επτά** συγκρίσεις και τελειώνει με `i = 8`.
3. **Εδώ φαίνεται γιατί χρειάζεται το `ΑΝ i <= n`:** με `i = 8` δεν υπάρχει `A[8]` να συγκριθεί με το $50$.

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

1. **Ζητούνται όλες οι εμφανίσεις**, όχι η πρώτη: `ΓΙΑ` σε όλο τον πίνακα, με μετρητή και αθροιστή.
2. **Η αναζήτηση γίνεται στον ΟΝ**, και το ποσό βγαίνει από τον **παράλληλο** πίνακα ΠΟΣΟ στην ίδια θέση `i`.

   *Διαδραστικό στη σελίδα: Αγορές ενός πελάτη*
3. **Έξοδος:** `Μαρία 3 60`. Για όνομα που λείπει, το `πλ` μένει $0$ και εμφανίζεται το μήνυμα.
4. **Το μήνυμα «δεν υπάρχει» μπαίνει μετά τον βρόχο**, όχι σε `ΑΛΛΙΩΣ` μέσα του. Μέσα θα τυπωνόταν μία φορά για κάθε άλλο πελάτη.

## Ερωτήσεις

1. Η δυαδική αναζήτηση προϋποθέτει ότι ο πίνακας είναι:
   - ταξινομημένος
   - μονοδιάστατος
   - χωρίς διπλότυπες τιμές
   - μεγέθους δύναμης του δύο
2. Πότε είναι η σειριακή αναζήτηση η σωστή επιλογή;
   - όταν ο πίνακας δεν είναι ταξινομημένος και η αναζήτηση γίνεται μία φορά
   - όταν ο πίνακας είναι πολύ μεγάλος, ταξινομημένος και ψάχνουμε πολλές φορές
   - ποτέ: η δυαδική είναι πάντα καλύτερη
   - μόνο όταν το ζητούμενο βρίσκεται στην πρώτη θέση
3. Σε ταξινομημένο πίνακα $1000$ στοιχείων, η δυαδική αναζήτηση χρειάζεται στη χειρότερη περίπτωση περίπου:
   - $10$ συγκρίσεις
   - $500$ συγκρίσεις
   - $1000$ συγκρίσεις
   - $100$ συγκρίσεις
4. Η σημαία στη σειριακή αναζήτηση χρησιμεύει ώστε:
   - να σταματήσει ο βρόχος μόλις βρεθεί το στοιχείο
   - να μετρηθούν οι συγκρίσεις που έγιναν
   - να ταξινομηθεί ο πίνακας πριν από την αναζήτηση
   - να αποφευχθεί η υπερχείλιση του πίνακα
5. Η στρατηγική «διαίρει και βασίλευε» έχει τα βήματα:
   - διαίρεση, κυριαρχία, σύνθεση
   - ταξινόμηση, αναζήτηση, εκτύπωση
   - κατανόηση, ανάλυση, επίλυση
   - είσοδος, επεξεργασία, έξοδος
6. Αν εφαρμοστεί δυαδική αναζήτηση σε μη ταξινομημένο πίνακα, τότε:
   - μπορεί να απαντήσει «δεν βρέθηκε» για στοιχείο που υπάρχει
   - δουλεύει σωστά, αλλά κάνει περισσότερες συγκρίσεις
   - ταξινομεί πρώτα τον πίνακα αυτόματα
   - τερματίζει με σφάλμα εκτέλεσης στην πρώτη σύγκριση που αποτυγχάνει
7. Πόσες συγκρίσεις κάνει η σειριακή αναζήτηση με σημαία σε πίνακα $50$ στοιχείων, όταν το ζητούμενο δεν υπάρχει;
   - $50$
   - $25$
   - $51$
   - $6$
8. Ζητείται να εμφανιστούν όλες οι θέσεις όπου υπάρχει το `key`. Ποια δομή ταιριάζει;
   - `ΓΙΑ` σε όλο τον πίνακα, χωρίς σημαία
   - `ΟΣΟ` με σημαία που σταματά στο εύρημα
   - δυαδική αναζήτηση, μία φορά
   - `ΓΙΑ` από το $n$ ως το $1$ με σημαία
9. Σε πίνακα ταξινομημένο σε αύξουσα σειρά, η σειριακή αναζήτηση μπορεί να σταματήσει νωρίς όταν:
   - βρει στοιχείο μεγαλύτερο ή ίσο από το `key`
   - βρει στοιχείο μικρότερο από το `key`
   - φτάσει στη μέση του πίνακα
   - βρει δύο ίσα γειτονικά στοιχεία
10. Σε μη ταξινομημένο πίνακα θα γίνουν χιλιάδες αναζητήσεις. Τι συμφέρει συνήθως;
   - ταξινόμηση μία φορά, και δυαδική κάθε φορά
   - σειριακή κάθε φορά, χωρίς ταξινόμηση
   - ταξινόμηση πριν από κάθε αναζήτηση
   - δυαδική κάθε φορά, χωρίς ταξινόμηση

## Ασκήσεις

1. Τι πρέπει να ισχύει για τον πίνακα ώστε να εφαρμοστεί δυαδική αναζήτηση;
2. Ποια μέθοδος αναζήτησης εφαρμόζεται σε πίνακα που δεν είναι ταξινομημένος;
3. Σε πίνακα $40$ στοιχείων γίνεται σειριακή αναζήτηση με σημαία, και το ζητούμενο βρίσκεται στη θέση $17$. Πόσες συγκρίσεις γίνονται;
4. Σε πίνακα $40$ στοιχείων εκτελείται το τμήμα «όλες οι εμφανίσεις», με `ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n`. Το ζητούμενο υπάρχει μόνο στη θέση $3$. Πόσες συγκρίσεις γίνονται;
5. Ο πίνακας Α έχει τις τιμές $6, 2, 6, 9, 6, 1$ και ψάχνεις το `key = 6`.
   α) Ποιες θέσεις εμφανίζει το τμήμα «όλες οι εμφανίσεις»;
   β) Ποια θέση κρατά το τμήμα με `ΑΝ A[i] = key ΤΟΤΕ θέση <- i` μέσα σε `ΓΙΑ`;
   γ) Πόσες συγκρίσεις κάνει η σειριακή με σημαία;
6. Ο πίνακας Α είναι ταξινομημένος: $3, 7, 10, 15, 22, 30, 41$. Εκτελείται η σειριακή αναζήτηση με πρόωρη στάση (σταματά στο πρώτο `A[i] >= key`).
   α) Πόσες συγκρίσεις γίνονται για `key = 15`;
   β) Πόσες συγκρίσεις γίνονται για `key = 41`;
   γ) Ποια είναι η τιμή του `i` στο τέλος για `key = 50`;
7. Δίνεται μη ταξινομημένος πίνακας $200$ ονομάτων και ζητούνται $500$ αναζητήσεις.
   α) Πόσες συγκρίσεις κάνει η φυσαλίδα για να τον ταξινομήσει;
   β) Πόσες το πολύ συγκρίσεις κάνουν συνολικά $500$ σειριακές αναζητήσεις;
   γ) Πόσες το πολύ συγκρίσεις κάνει μία δυαδική αναζήτηση στον ταξινομημένο πίνακα;
   δ) Ποια μέθοδο επιλέγεις;
8. Ένας μη ταξινομημένος πίνακας έχει $300$ κωδικούς. Συγκρίνεις τις χειρότερες περιπτώσεις: σειριακή κάθε φορά, ή φυσαλίδα μία φορά και μετά δυαδική.
   α) Πόσες συγκρίσεις κάνει η φυσαλίδα;
   β) Πόσες το πολύ συγκρίσεις κάνει μία δυαδική αναζήτηση;
   γ) Από πόσες αναζητήσεις και πάνω συμφέρει η ταξινόμηση;

---

Οι απαντήσεις, τα διαδραστικά και τα παιχνίδια είναι στη σελίδα της ενότητας: https://www.akademio.gr/el/lyk-c/informatics/searching-sorting
