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

> Πώς βρίσκεις μια τιμή σε ταξινομημένη λίστα κόβοντας στη μέση, και πόσα βήματα θέλει.

Προγραμματισμός Υπολογιστών, Γ΄ ΕΠΑΛ. https://www.akademio.gr/el/epal-c/programming/binary-search

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

- Να εξηγείς γιατί η δυαδική αναζήτηση χρειάζεται ταξινομημένη λίστα και πώς μειώνει στο μισό τον χώρο αναζήτησης.
- Να γράφεις τη συνάρτηση binarySearch του βιβλίου σε Python, και στις δύο μορφές της (με found και με pos).
- Να εκτελείς τον αλγόριθμο με το χέρι, με τις τιμές των first, last και mid σε κάθε επανάληψη, και όταν το στοιχείο λείπει.
- Να βρίσκεις πόσα στοιχεία εξετάζονται το πολύ σε λίστα N στοιχείων, και να προσαρμόζεις τον αλγόριθμο σε φθίνουσα σειρά.

## Βρες τον αριθμό

Σκέψου έναν αριθμό από το $1$ ως το $1000$. Η πρώτη ερώτηση είναι: «Είναι μικρότερος από το $500$;». Όποια κι αν είναι η απάντηση, μένουν $500$ υποψήφιοι αντί για $1000$. Η δεύτερη ερώτηση, για το $250$ ή για το $750$, αφήνει $250$. Κάθε ερώτηση κόβει τον **χώρο αναζήτησης** στο μισό.

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

## Ο υπολογιστής μαντεύει

Στο βιβλίο ο υπολογιστής μαντεύει τον αριθμό που σκέφτεσαι. Χρειάζεται τρεις μεταβλητές: τα δύο άκρα του διαστήματος, `first` και `last`, και το μέσο του, `mid`. Κάθε απάντηση μετακινεί **ένα** από τα δύο άκρα.

> **Στον υπολογιστή σου, με Python 3**
>
> Το βιβλίο και οι εξετάσεις γράφουν Python 2.7. Στην Python 3 γράφεις `print(x)` αντί για `print x` και `input()` αντί για `raw_input()`. Το `input()` της 3 δίνει πάντα κείμενο, άρα για αριθμό γράφεις `int(input())`. Και το `/` δίνει πάντα δεκαδικό (`17 / 2` κάνει `8.5`), οπότε το μέσο γράφεται `mid = (first + last) // 2`.

```python
# Ο άνθρωπος σκέφτεται έναν αριθμό από 1 έως 1000
N = 1000
print "Σκέψου έναν αριθμό από το 1 έως το", N
guesses = 0
found = False
first = 1
last = N
while not found and guesses < 10:
    mid = (first + last) / 2
    answer = raw_input("Είναι ο αριθμός ο " + str(mid) + " ? (N/O)")
    guesses = guesses + 1
    if answer == "N":
        found = True
    else:
        answer = raw_input("Είναι μικρότερος του " + str(mid) + " ?")
        if answer == "N":
            last = mid - 1
        else:
            first = mid + 1
if found:
    print "Κέρδισα!!! Το βρήκα με", guesses, "προσπάθειες"
else:
    print "Κέρδισες"
```

Στην Python 2.7 το `/` ανάμεσα σε ακέραιους είναι **ακέραιη διαίρεση**: το `(1 + 1000) / 2` κάνει `500`, όχι `500.5`. Έτσι το `mid` είναι πάντα ακέραιος. Το βιβλίο δείχνει το ίδιο παιχνίδι στο διάστημα $1$ ως $16$, με μυστικό αριθμό το $11$:

*Διαδραστικό στη σελίδα: Ο υπολογιστής βρίσκει το 11 από το 1 ως το 16*

Οι μέσες ήταν $8$, $12$, $10$ και $11$: τέσσερις ερωτήσεις αντί για δεκαέξι. Με $1000$ αριθμούς αρκούν $10$, γιατί $2^{10} = 1024$.

> **Πρόσεχε**
>
> **Σε μη ταξινομημένη λίστα η δυαδική αναζήτηση δεν βγάζει μήνυμα λάθους: δίνει λάθος απάντηση.** Στη `[8, 3, 5, 1, 9]` με `key = 1`, το πρώτο `mid` είναι $2$ και το $5 > 1$ στέλνει την αναζήτηση αριστερά. Εκεί εξετάζεται το $8$, το διάστημα αδειάζει, και το $1$ «δεν υπάρχει», ενώ είναι στη θέση $3$.

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

Η ίδια ιδέα δουλεύει σε μια λίστα `array`, αρκεί τα στοιχεία της να είναι **ταξινομημένα**. Τα άκρα τώρα είναι **θέσεις** της λίστας: ξεκινούν από `0` και `len(array) - 1`. Αυτή είναι η συνάρτηση του βιβλίου, για λίστα σε **αύξουσα** σειρά:

```python
def binarySearch(array, key):
    first = 0
    last = len(array) - 1
    found = False
    while first <= last and not found:
        mid = (first + last) / 2
        if array[mid] == key:
            found = True
        elif array[mid] < key:
            first = mid + 1
        else:
            last = mid - 1
    return found
```

Επιστρέφει `True` αν το `key` υπάρχει στη λίστα και `False` αν όχι. Τις περισσότερες φορές όμως θέλεις και τη **θέση** του. Στη δεύτερη μορφή η λογική μεταβλητή `found` αντικαθίσταται από τη `pos`, που ξεκινά από `-1`. Όσο μένει `-1`, το στοιχείο δεν έχει βρεθεί. Μόλις βρεθεί, κρατά τη θέση του.

Στον runner που ακολουθεί το μέσο γράφεται `(first + last) // 2`, που δίνει το ίδιο αποτέλεσμα με το `(first + last) / 2` του βιβλίου στην 2.7. Το `print(...)` με ένα όρισμα δουλεύει ίδια και στις δύο εκδόσεις.

*Διαδραστικό στη σελίδα: Η θέση του 45 σε 14 αριθμούς*

*Διαδραστικό στη σελίδα: Τα first, last και mid για το 45*

> **Κλειδί**
>
> **Κάθε επανάληψη εξετάζει ένα στοιχείο, το `array[mid]`, και έχει τρεις εξόδους:**
>
> - `array[mid] == key`: βρέθηκε, και ο βρόχος σταματά.
> - `array[mid] < key`: το ζητούμενο είναι **δεξιά**, άρα `first = mid + 1`.
> - αλλιώς είναι **αριστερά**, άρα `last = mid - 1`.
>
> Τα άκρα πάνε **μία θέση πέρα** από το `mid`, γιατί το `mid` έχει ήδη εξεταστεί. Ο βρόχος σταματά είτε όταν βρεθεί το στοιχείο είτε όταν `first > last`, δηλαδή όταν το διάστημα αδειάσει.

## Όταν το στοιχείο δεν υπάρχει

Στην ίδια λίστα ψάχνεις το $33$, που λείπει.

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

Ο αλγόριθμος ισχύει για κάθε τύπο δεδομένων που συγκρίνεται με `==` και `<`: ακέραιους, πραγματικούς, και συμβολοσειρές σε αλφαβητική σειρά. Έτσι βρίσκεις ένα όνομα σε τηλεφωνικό κατάλογο.

## Πόσα στοιχεία εξετάζονται

Κάθε επανάληψη κρατά το πολύ το μισό διάστημα. Για λίστα $N$ στοιχείων, η χειρότερη περίπτωση βγαίνει χωρίς λογάριθμο: βρες τη **μικρότερη δύναμη του $2$ που ξεπερνά το $N$**. Αν είναι $2^k$, εξετάζονται το πολύ $k$ στοιχεία.

| Στοιχεία $N$      | $7$ | $14$ | $16$ | $100$ | $1000$ | $1.000.000$ |
| ----------------- | --- | ---- | ---- | ----- | ------ | ----------- |
| Σειριακή, το πολύ | $7$ | $14$ | $16$ | $100$ | $1000$ | $1.000.000$ |
| Δυαδική, το πολύ  | $3$ | $4$  | $5$  | $7$   | $10$   | $20$        |

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

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

## Φθίνουσα σειρά

Αν η λίστα είναι ταξινομημένη από το μεγαλύτερο στο μικρότερο, οι **μικρότερες** τιμές είναι δεξιά. Όταν `array[mid] > key`, το ζητούμενο είναι δεξιά. Αλλάζει μόνο ο τελεστής της `elif`:

```python
if array[mid] == key:
    pos = mid
elif array[mid] > key:
    first = mid + 1
else:
    last = mid - 1
```

Οι αναθέσεις στα `first` και `last` μένουν ίδιες.

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

### Παράδειγμα 1: Δίνεται η λίστα A = \[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 94, 96, 99]. Να γράψετε τους αριθμούς που θα συγκριθούν με το 100 κατά την εκτέλεση της δυαδικής αναζήτησης, και τι θα επιστρέψει η συνάρτηση με τη pos.

1. **Πρώτη επανάληψη:** `first = 0`, `last = 13`, `mid = (0 + 13) / 2 = 6`, με ακέραιη διαίρεση. Είναι `A[6] = 13 < 100`, άρα `first = 7`.
2. **Δεύτερη:** `mid = (7 + 13) / 2 = 10`, `A[10] = 89 < 100`, `first = 11`. **Τρίτη:** `mid = 12`, `A[12] = 96 < 100`, `first = 13`.
3. **Τέταρτη:** `mid = 13`, `A[13] = 99 < 100`, `first = 14`. Τώρα `first > last` και ο βρόχος σταματά.
4. **Συγκρίθηκαν οι $13$, $89$, $96$, $99$:** τέσσερις συγκρίσεις. Η `pos` έμεινε `-1`, και αυτό επιστρέφεται.

### Παράδειγμα 2: Να συμπληρώσετε τα κενά (1) ως (5), ώστε η συνάρτηση να εκτελεί δυαδική αναζήτηση του key στη λίστα array, σε αύξουσα σειρά.

1. ```python
   def binarySearch(array, key):
       first = 0
       last = (1)
       found = False
       while first <= last and (2):
           mid = (3)
           if array[mid] == key:
               found = True
           elif array[mid] < key:
               first = (4)
           else:
               last = (5)
       return found
   ```
2. **(1)** `len(array) - 1`, η τελευταία θέση. **(2)** `not found`: ο βρόχος συνεχίζει όσο δεν έχει βρεθεί.
3. **(3)** `(first + last) / 2`, που ανάμεσα σε ακέραιους δίνει ακέραιο πηλίκο. **(4)** `mid + 1` και **(5)** `mid - 1`: το `mid` έχει εξεταστεί και μένει έξω.

### Παράδειγμα 3: Η λίστα codes έχει τους κωδικούς 7 προϊόντων σε αύξουσα σειρά και η prices τις τιμές τους, στις ίδιες θέσεις. Να γράψετε πρόγραμμα σε Python που διαβάζει κωδικούς μέχρι να δοθεί 0 και εμφανίζει για τον καθένα την τιμή του ή «Δεν υπάρχει».

1. **Η αναζήτηση γίνεται στη `codes`**, που είναι ταξινομημένη. Η δεύτερη μορφή της `binarySearch` δίνει τη θέση, και η τιμή βρίσκεται στην **ίδια θέση** της `prices`.
2. **Ο βρόχος είναι `while`** με τιμή τερματισμού το $0$: μία ανάγνωση πριν από αυτόν και μία στο τέλος του μπλοκ.
   ```python
   def binarySearch(array, key):
       first = 0
       last = len(array) - 1
       pos = -1
       while first <= last and pos == -1:
           mid = (first + last) / 2
           if array[mid] == key:
               pos = mid
           elif array[mid] < key:
               first = mid + 1
           else:
               last = mid - 1
       return pos

   codes = [104, 117, 125, 138, 142, 156, 171]
   prices = [2.5, 4.0, 1.2, 7.8, 3.0, 12.5, 6.0]
   code = input("Κωδικός: ")
   while code != 0:
       pos = binarySearch(codes, code)
       if pos != -1:
           print "Τιμή:", prices[pos]
       else:
           print "Δεν υπάρχει"
       code = input("Κωδικός: ")
   ```
3. **Για τους κωδικούς 138, 120, 171 και 0** εμφανίζει `Τιμή: 7.8`, `Δεν υπάρχει`, `Τιμή: 6.0`. Κάθε κλήση ξεκινά πάλι με `first = 0` και `last = 6`, γιατί είναι τοπικές μεταβλητές της συνάρτησης. Η `input` δίνει αριθμό, όπως στο βιβλίο. Ο έλεγχος γίνεται με `pos != -1` και όχι με `if pos:`, γιατί ένα προϊόν στη θέση $0$ θα έδινε `0`, που η Python το διαβάζει ως ψευδές.

> **Θυμήσου**
>
> - Η δυαδική αναζήτηση θέλει **ταξινομημένη** λίστα. Σε μη ταξινομημένη, πρώτα ταξινομείς.
> - `first = 0`, `last = len(array) - 1`, `mid = (first + last) / 2` (στην Python 3, `//`).
> - `first = mid + 1` όταν το ζητούμενο είναι δεξιά, `last = mid - 1` όταν είναι αριστερά.
> - Επιστρέφει `True`/`False` (με `found`) ή τη θέση/`-1` (με `pos`).
> - Σε $N$ στοιχεία εξετάζει το πολύ $k$, όπου $2^k$ η μικρότερη δύναμη του $2$ πάνω από το $N$.

## Ερωτήσεις

1. Σωστό ή Λάθος: «Η δυαδική αναζήτηση μπορεί να εφαρμοστεί σε οποιαδήποτε λίστα αριθμών.»
   - Λάθος, η λίστα πρέπει να είναι ταξινομημένη
   - Σωστό, αρκεί οι αριθμοί να είναι ακέραιοι
   - Σωστό, αρκεί η λίστα να μην έχει διπλές τιμές
   - Λάθος, δουλεύει μόνο σε λίστες με ζυγό πλήθος
2. Σε μια επανάληψη της συνάρτησης του βιβλίου είναι first = 7 και last = 14. Ποια τιμή παίρνει η mid = (first + last) / 2;
   - 10
   - 10.5
   - 3
   - 11
3. Πόσα στοιχεία εξετάζει η δυαδική αναζήτηση στην καλύτερη περίπτωση, και πότε συμβαίνει αυτό;
   - Ένα, όταν το key είναι στη μεσαία θέση
   - Ένα, όταν το key είναι στην πρώτη θέση
   - Κανένα, όταν η λίστα έχει ένα στοιχείο
   - Δύο, όταν το key είναι δίπλα στη μέση
4. Στη συνάρτηση του βιβλίου, η λίστα είναι σε αύξουσα σειρά και ισχύει array[mid] < key. Ποια εντολή εκτελείται;
   - first = mid + 1
   - last = mid - 1
   - first = mid
   - last = mid + 1
5. Τι εμφανίζει η print binarySearch([3, 8, 12, 15, 21], 15), με τη μορφή του βιβλίου που επιστρέφει τη pos;
   - 3
   - 4
   - True
   - 2
6. Η αναζήτηση ενός key που δεν υπάρχει στη λίστα τελειώνει. Ποια συνθήκη έγινε ψευδής;
   - Η first <= last, γιατί έγινε first > last
   - Η pos == -1, γιατί η pos άλλαξε τιμή
   - Καμία, ο βρόχος σταματά με break
   - Η mid < len(array), γιατί το mid βγήκε εκτός
7. Σωστό ή Λάθος: «Σε ταξινομημένη λίστα 1000 στοιχείων, η δυαδική αναζήτηση εξετάζει το πολύ 10 στοιχεία.»
   - Σωστό, γιατί 2 στη δέκατη είναι 1024
   - Λάθος, εξετάζει το πολύ 500 στοιχεία
   - Λάθος, εξετάζει το πολύ 100 στοιχεία
   - Λάθος, εξαρτάται από το πού είναι το key
8. Μια ταξινομημένη λίστα μεγαλώνει από 500 σε 1000 στοιχεία. Πώς αλλάζει το μέγιστο πλήθος στοιχείων που εξετάζει η δυαδική αναζήτηση;
   - Αυξάνεται κατά ένα
   - Διπλασιάζεται
   - Μένει ακριβώς ίδιο
   - Αυξάνεται κατά 500
9. Η λίστα είναι ταξινομημένη σε φθίνουσα σειρά. Ποια αλλαγή χρειάζεται στη συνάρτηση του βιβλίου;
   - Η elif γίνεται array[mid] > key, με τα ίδια σώματα
   - Η mid γίνεται (first + last) / 2 + 1, όλα τα άλλα ίδια
   - Τα first και last ξεκινούν ανάποδα, με τις ίδιες συγκρίσεις
   - Καμία, η ίδια συνάρτηση δουλεύει και στις δύο σειρές
10. Τι εμφανίζει η print binarySearch(["Γιάννης", "Ελένη", "Κώστας", "Νίκος", "Σοφία"], "Νίκος"), με τη μορφή του βιβλίου που επιστρέφει τη found;
   - True
   - 3
   - False
   - TypeError

## Ασκήσεις

1. Στη λίστα A = [4, 9, 15, 22, 31, 40, 52] εκτελείται δυαδική αναζήτηση. Ποιο στοιχείο εξετάζεται πρώτο, και σε ποια θέση είναι;
2. Στην ίδια λίστα A = [4, 9, 15, 22, 31, 40, 52] ψάχνεις το 40 με τη binarySearch που επιστρέφει τη pos. Ποια στοιχεία εξετάζονται, με τη σειρά, και τι επιστρέφει η συνάρτηση;
3. Ποιο είναι το μεγαλύτερο πλήθος στοιχείων μιας ταξινομημένης λίστας για το οποίο η δυαδική αναζήτηση εξετάζει το πολύ 6 στοιχεία;
4. Στη λίστα A = [4, 9, 15, 22, 31, 40, 52] ψάχνεις το 10, που δεν υπάρχει.
   α) Ποια στοιχεία εξετάζονται, με τη σειρά;
   β) Ποιες είναι οι τιμές των first και last όταν τελειώνει ο βρόχος;
5. Ένας μαθητής γράφει στη binarySearch last = mid αντί για last = mid - 1, και τα υπόλοιπα όπως το βιβλίο. Δοκιμάζει τη λίστα A = [4, 9, 15, 22, 31, 40, 52].
   α) Τι επιστρέφει η binarySearch(A, 22);
   β) Τι γίνεται με τη binarySearch(A, 3);
6. Μια ταξινομημένη λίστα έχει 15 διαφορετικά στοιχεία, στις θέσεις 0 ως 14. Για ποιες θέσεις του ζητούμενου η δυαδική αναζήτηση εξετάζει ακριβώς 4 στοιχεία;

---

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