# Αναζήτηση

> Σειριακή και δυαδική αναζήτηση, και πόσα βήματα κάνει η καθεμία.

Πληροφορική, Γ΄ Γυμνασίου. https://www.akademio.gr/el/gym-c/informatics/search-algorithms

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

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

## Ψάχνοντας μέσα σε δεδομένα

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

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

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

Η πιο απλή ιδέα: ξεκινάς από την αρχή και ελέγχεις τα στοιχεία **ένα ένα**, μέχρι να βρεις τον στόχο ή να τελειώσει η λίστα. Λέγεται **σειριακή** ή **γραμμική** αναζήτηση (linear search).

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

Η συνάρτηση επιστρέφει τη **θέση** του στόχου. Αν δεν τον βρει, επιστρέφει `-1`, μια τιμή που δεν μπορεί να είναι θέση και άρα σημαίνει «δεν υπάρχει». Πρόσεξε ότι το `return -1` είναι **έξω** από τον βρόχο: εκτελείται μόνο αν ο βρόχος τελειώσει χωρίς να βρει τίποτα.

| Στόχος | Στοιχεία που εξετάστηκαν | Συγκρίσεις                 |
| ------ | ------------------------ | -------------------------- |
| `42`   | `42`                     | $1$: η καλύτερη περίπτωση  |
| `88`   | `42, 7, 19, 88`          | $4$                        |
| `5`    | όλα, χωρίς επιτυχία      | $6$: η χειρότερη περίπτωση |

**Χειρότερη περίπτωση** είναι όταν ο στόχος είναι τελευταίος ή δεν υπάρχει καθόλου. Τότε η σειριακή αναζήτηση κάνει **τόσες συγκρίσεις όσα είναι τα στοιχεία**: για λίστα με $n$ στοιχεία, $n$ συγκρίσεις.

Το μεγάλο πλεονέκτημά της: **δουλεύει σε οποιαδήποτε λίστα**, ταξινομημένη ή όχι.

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

Σκέψου πώς ψάχνεις μια λέξη σε ένα έντυπο λεξικό. Δεν ξεκινάς από τη σελίδα $1$. Ανοίγεις κάπου στη μέση, βλέπεις ότι η λέξη σου είναι «πιο πριν», και **πετάς όλο το δεύτερο μισό**. Αυτό γίνεται μόνο επειδή το λεξικό είναι σε **αλφαβητική σειρά**.

Η **δυαδική αναζήτηση** (binary search) κάνει ακριβώς αυτό σε μια **ταξινομημένη** λίστα:

1. Κοιτάζει το **μεσαίο** στοιχείο του τμήματος που απομένει.
2. Αν είναι ο στόχος, τελείωσε.
3. Αν είναι **μικρότερο** από τον στόχο, ο στόχος μόνο στο **δεξί** μισό μπορεί να είναι. Αν είναι **μεγαλύτερο**, μόνο στο **αριστερό**.
4. Επαναλαμβάνει στο μισό που έμεινε, μέχρι να βρει τον στόχο ή να μη μείνει τίποτα.

```python
def dyadiki(lista, stoxos):
    arxi = 0
    telos = len(lista) - 1
    while arxi <= telos:
        mesi = (arxi + telos) // 2
        if lista[mesi] == stoxos:
            return mesi
        elif lista[mesi] < stoxos:
            arxi = mesi + 1
        else:
            telos = mesi - 1
    return -1

taxin = [3, 8, 12, 17, 23, 31, 40, 52, 66]
print(dyadiki(taxin, 40))
print(dyadiki(taxin, 20))
```

```text
6
-1
```

Οι μεταβλητές `arxi` και `telos` είναι οι δείκτες που οριοθετούν το κομμάτι της λίστας όπου μπορεί ακόμη να βρίσκεται ο στόχος. Η μέση υπολογίζεται με `//`, γιατί ο δείκτης πρέπει να είναι ακέραιος. Όταν το `arxi` ξεπεράσει το `telos`, το κομμάτι άδειασε και ο στόχος δεν υπάρχει.

*Διαδραστικό στη σελίδα: Πίνακας βημάτων: δυαδική αναζήτηση του 20*

> **Κλειδί**
>
> **Κάθε σύγκριση της δυαδικής αναζήτησης πετάει τη μισή λίστα.**
>
> Γι' αυτό, όταν η λίστα διπλασιάζεται, η δυαδική χρειάζεται μόνο **μία** σύγκριση παραπάνω. Στη χειρότερη περίπτωση κάνει $k$ συγκρίσεις, όπου $k$ είναι ο μικρότερος ακέραιος με $2^k > n$.
>
> Για $n = 1000$ είναι $k = 10$, γιατί $2^{10} = 1024$. Για ένα εκατομμύριο στοιχεία, μόλις $20$.

| Στοιχεία $n$  | Σειριακή, χειρότερη | Δυαδική, χειρότερη |
| ------------- | ------------------- | ------------------ |
| $10$          | $10$                | $4$                |
| $100$         | $100$               | $7$                |
| $1000$        | $1000$              | $10$               |
| $1\,000\,000$ | $1\,000\,000$       | $20$               |

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

> **Πρόσεχε**
>
> **Σε μη ταξινομημένη λίστα η δυαδική αναζήτηση δεν είναι απλώς αργή: δίνει λάθος απάντηση.**
>
> Στη λίστα `[42, 7, 19, 88, 3, 56]`, αν ψάξεις το `7`, η πρώτη μέση είναι το `19` (θέση $2$). Επειδή $19 > 7$, ο αλγόριθμος πετάει το δεξί κομμάτι και συνεχίζει στο `[42, 7]`. Εξετάζει το `42`, και επειδή $42 > 7$, κρατά ένα κομμάτι που δεν έχει κανένα στοιχείο. Απαντά «δεν βρέθηκε», ενώ το `7` είναι εκεί, στη θέση $1$.

Άρα η επιλογή έχει κόστος: αν η λίστα αλλάζει συνέχεια και ψάχνεις σπάνια, ίσως δεν αξίζει να την ταξινομείς κάθε φορά. Αν ψάχνεις συχνά στα ίδια δεδομένα, η ταξινόμηση πληρώνεται μία φορά και κερδίζεται σε κάθε αναζήτηση. Γι' αυτό η επόμενη ενότητα είναι η **ταξινόμηση**.

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

### Παράδειγμα 1: Ψάξε με δυαδική αναζήτηση το 40 στη λίστα \[3, 8, 12, 17, 23, 31, 40, 52, 66]. Πόσες συγκρίσεις χρειάζονται;

1. **Βήμα 1:** `arxi = 0`, `telos = 8`, άρα `mesi = (0 + 8) // 2 = 4`. Στη θέση $4$ είναι το `23`. Επειδή $23 < 40$, ο στόχος είναι δεξιά: `arxi = 5`.
2. **Βήμα 2:** `arxi = 5`, `telos = 8`, άρα `mesi = (5 + 8) // 2 = 6`. Το `//` κόβει το $6{,}5$ σε $6$. Στη θέση $6$ είναι το `40`: **βρέθηκε**.
3. **Αποτέλεσμα:** η συνάρτηση επιστρέφει `6`, μετά από **2** συγκρίσεις.

   Η σειριακή αναζήτηση θα εξέταζε τα `3, 8, 12, 17, 23, 31, 40`: **7** συγκρίσεις.

### Παράδειγμα 2: Ένας κατάλογος έχει 500 ταξινομημένα ονόματα. Πόσες συγκρίσεις χρειάζεται στη χειρότερη περίπτωση η σειριακή και πόσες η δυαδική αναζήτηση;

1. **Σειριακή:** στη χειρότερη περίπτωση εξετάζει όλα τα στοιχεία, άρα **500** συγκρίσεις.
2. **Δυαδική:** ψάχνουμε τον μικρότερο $k$ με $2^k > 500$. Είναι $2^8 = 256$, που δεν φτάνει, και $2^9 = 512$, που ξεπερνά το $500$.
3. **Άρα 9 συγκρίσεις.** Ένας άλλος τρόπος να το δεις: κάθε σύγκριση μοιράζει στη μέση το κομμάτι που μένει, περίπου $500 \to 250 \to 125 \to 62 \to 31 \to 15 \to 7 \to 3 \to 1$. Αυτά είναι εννέα κομμάτια, άρα εννέα στοιχεία εξετάζονται.
4. **Σύγκριση:** $500$ έναντι $9$. Για λίστα διπλάσια, $1000$ στοιχείων, η σειριακή θα χρειαζόταν $1000$ και η δυαδική μόνο $10$.

> **Θυμήσου**
>
> - **Σειριακή:** ένα ένα από την αρχή. Δουλεύει σε κάθε λίστα. Χειρότερη περίπτωση: $n$ συγκρίσεις.
> - **Δυαδική:** κοιτάζει τη μέση και πετάει το μισό. Θέλει **ταξινομημένη** λίστα. Χειρότερη περίπτωση: ο μικρότερος $k$ με $2^k > n$.
> - Η τιμή `-1` επιστρέφεται όταν ο στόχος δεν υπάρχει.

## Ερωτήσεις

1. Πόσες συγκρίσεις κάνει η σειριακή αναζήτηση στη χειρότερη περίπτωση, σε λίστα με 50 στοιχεία;
   - 50
   - 25
   - 6
   - 1
2. Ποια προϋπόθεση πρέπει να ισχύει για να δώσει σωστό αποτέλεσμα η δυαδική αναζήτηση;
   - η λίστα να είναι ταξινομημένη
   - η λίστα να έχει άρτιο πλήθος στοιχείων
   - ο στόχος να υπάρχει στη λίστα
   - η λίστα να έχει τουλάχιστον 100 στοιχεία
3. Σε λίστα με 9 στοιχεία (δείκτες 0 ως 8), ποιον δείκτη εξετάζει πρώτο η δυαδική αναζήτηση;
   - 4
   - 0
   - 4.5
   - 5
4. Πόσες συγκρίσεις χρειάζεται στη χειρότερη περίπτωση η δυαδική αναζήτηση σε 200 ταξινομημένα στοιχεία;
   - 8
   - 100
   - 20
   - 200
5. Η συνάρτηση seiriaki επιστρέφει -1. Τι σημαίνει αυτό;
   - ο στόχος δεν υπάρχει στη λίστα
   - ο στόχος είναι το τελευταίο στοιχείο
   - ο στόχος βρέθηκε στην πρώτη θέση
   - έγινε σφάλμα στο πρόγραμμα
6. Μια ταξινομημένη λίστα μεγαλώνει από 1000 σε 2000 στοιχεία. Πόσες συγκρίσεις χρειάζεται τώρα η δυαδική αναζήτηση στη χειρότερη περίπτωση;
   - 11
   - 20
   - 10
   - 2000
7. Με δυαδική αναζήτηση του 27 στη λίστα [2, 5, 9, 14, 20, 27, 33], πόσες συγκρίσεις γίνονται;
   - 2
   - 6
   - 1
   - 3
8. Στη δυαδική αναζήτηση, το στοιχείο στη μέση είναι μικρότερο από τον στόχο. Τι κάνει ο αλγόριθμος;
   - arxi = mesi + 1
   - telos = mesi - 1
   - arxi = mesi
   - σταματά και επιστρέφει -1
9. Κάποιος γράφει στη seiriaki ένα else: return -1 μέσα στον βρόχο, κάτω από το if. Τι επιστρέφει η seiriaki([4, 9, 1, 7], 7);
   - -1
   - 3
   - 0
   - σφάλμα σύνταξης
10. Σε ποια περίπτωση η σειριακή αναζήτηση είναι λογική επιλογή;
   - σε μια μικρή, μη ταξινομημένη λίστα όπου ψάχνεις μία φορά
   - σε ένα τεράστιο ταξινομημένο ευρετήριο όπου γίνονται χιλιάδες αναζητήσεις
   - ποτέ, γιατί η δυαδική είναι πάντα καλύτερη
   - μόνο όταν ο στόχος είναι σίγουρα στην πρώτη θέση

## Ασκήσεις

1. Πόσες συγκρίσεις κάνει η σειριακή αναζήτηση για να βρει το 19 στη λίστα [42, 7, 19, 88, 3, 56];
2. Πόσες συγκρίσεις χρειάζεται στη χειρότερη περίπτωση η δυαδική αναζήτηση σε 60 ταξινομημένα στοιχεία;
3. Εκτελείς δυαδική αναζήτηση του 1 στη λίστα [2, 5, 9, 14, 20, 27, 33].
   α) Ποιους δείκτες εξετάζει, με τη σειρά;
   β) Τι επιστρέφει η συνάρτηση dyadiki;
4. Μια εφαρμογή έχει 4000 επαφές.
   α) Οι επαφές είναι αποθηκευμένες με τη σειρά που προστέθηκαν, χωρίς ταξινόμηση. Ποια αναζήτηση μπορεί να χρησιμοποιήσει, και πόσες συγκρίσεις κάνει στη χειρότερη περίπτωση;
   β) Η εφαρμογή ταξινομεί τις επαφές και οι επαφές φτάνουν τις 9000. Πόσες συγκρίσεις κάνει τώρα η δυαδική στη χειρότερη περίπτωση;
   γ) Ποιο είναι το μεγαλύτερο πλήθος ταξινομημένων επαφών για το οποίο η δυαδική χρειάζεται το πολύ 12 συγκρίσεις στη χειρότερη περίπτωση;

---

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