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

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

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

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

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

## Ο αλγόριθμος του βιβλίου

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

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

Κάθε γραμμή έχει λόγο ύπαρξης:

- Η **γραμμή 6** βρίσκει τη μέση με ακέραια διαίρεση. Το `DIV` κόβει το δεκαδικό: για `first = 7`, `last = 8` δίνει `mid = 7`.
- Οι **γραμμές 8 και 10** μετακινούν το όριο **μία θέση πέρα** από τη μέση. Η μέση έχει ήδη εξεταστεί, δεν χρειάζεται να μείνει μέσα.
- Η **σημαία** `done` σταματά τον βρόχο μόλις βρεθεί το στοιχείο. Το `first <= last` τον σταματά όταν το διάστημα αδειάσει.

> **Κλειδί**
>
> **Ο πίνακας τιμών της δυαδικής έχει πάντα τις ίδιες στήλες:** `first`, `last`, `mid`, `A[mid]`, και τι έγινε.
>
> Γράφεις μία γραμμή για κάθε επανάληψη. Υπολογίζεις το `mid` από τα `first` και `last` της γραμμής, συγκρίνεις το `key` με το `A[mid]`, και αλλάζεις **μόνο ένα** από τα τρία: το `last`, το `first`, ή τη σημαία. Τα άλλα αντιγράφονται στην επόμενη γραμμή.

## Βήμα βήμα, με πίνακα τιμών

Ο ίδιος πίνακας, το ίδιο `key = 34`. Πες τι θα αλλάξει πριν πατήσεις.

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

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

Τώρα ψάχνεις το $10$, που δεν είναι στον πίνακα.

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

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

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

> **Πρόσεχε**
>
> **Μην κρίνεις από το `mid` μετά τον βρόχο.** Αν το στοιχείο δεν βρέθηκε, το `mid` έχει κι αυτό τιμή: την τελευταία μέση που υπολογίστηκε, μια κανονική θέση του πίνακα. Την απάντηση τη δίνει η σημαία.
>
> Και δύο λάθη που κάνουν τον βρόχο ατέρμονα: `last <- mid` αντί για `mid - 1`, και `first <- mid` αντί για `mid + 1`. Με `first = last = mid`, κανένα από τα δύο δεν αλλάζει ποτέ.

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

Κάθε επανάληψη εξετάζει ένα στοιχείο, το `A[mid]`, και κρατά το πολύ το μισό διάστημα. Για πίνακα $n$ στοιχείων, η **χειρότερη περίπτωση** είναι

$$
\lfloor \log_2 n \rfloor + 1
$$

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

| $n$                 | $7$ | $8$ | $15$ | $16$ | $100$ | $1000$ | $1024$ |
| ------------------- | --- | --- | ---- | ---- | ----- | ------ | ------ |
| χειρότερη περίπτωση | $3$ | $4$ | $4$  | $5$  | $7$   | $10$   | $11$   |

Η καλύτερη περίπτωση είναι **μία** επανάληψη: το `key` είναι ακριβώς στη μέση.

> **Θυμήσου**
>
> Διπλασίασε τον πίνακα και η δυαδική χρειάζεται **μία** επανάληψη παραπάνω. Η σειριακή χρειάζεται διπλάσιες.
>
> Γι' αυτό σε $1000$ στοιχεία η σειριακή κάνει στη χειρότερη περίπτωση $1000$ συγκρίσεις και η δυαδική $10$. Το κόστος όμως είναι ο ταξινομημένος πίνακας: αν δεν είναι ήδη, η ταξινόμηση κοστίζει πολύ περισσότερο από μία αναζήτηση.

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

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

*Διαδραστικό στη σελίδα: Δυαδική σε φθίνουσα σειρά*

Οι αναθέσεις στα `first` και `last` μένουν ίδιες. Αλλάζει μόνο το **πότε** γίνεται η καθεμιά.

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

### Παράδειγμα 1: Θέμα Β. Ο πίνακας Α έχει τις τιμές 7, 11, 16, 20, 25, 31, 38, 44, 50. Να γράψεις τον πίνακα τιμών της δυαδικής αναζήτησης για key = 16, και την τελική τιμή του position.

1. *Διαδραστικό στη σελίδα: Τα first, last και mid για το 16*
2. **Τρεις επαναλήψεις**, `position = 3`. Στη δεύτερη γραμμή, $(1 + 4)\ DIV\ 2 = 2$: το δεκαδικό κόβεται, δεν στρογγυλεύεται.

### Παράδειγμα 2: Στον ίδιο πίνακα 7, 11, 16, 20, 25, 31, 38, 44, 50 ψάχνεις το 45. Πόσα στοιχεία εξετάζονται, και με ποιες τιμές των first και last τελειώνει ο βρόχος;

1. **Πρώτη επανάληψη:** `mid = 5`, $45 > 25$, `first ← 6`. **Δεύτερη:** `mid = (6 + 9) DIV 2 = 7`, $45 > 38$, `first ← 8`.
2. **Τρίτη:** `mid = 8`, $45 > 44$, `first ← 9`. **Τέταρτη:** `mid = 9`, $45 < 50$, `last ← 8`.
3. **Τέσσερα στοιχεία:** $25, 38, 44, 50$. Ο βρόχος τελειώνει με `first = 9` και `last = 8`, και η σημαία `ΨΕΥΔΗΣ`. Το $45$ θα έμπαινε στη θέση $9$, ανάμεσα στο $44$ και στο $50$.

### Παράδειγμα 3: Πόσα στοιχεία εξετάζει στη χειρότερη περίπτωση η δυαδική αναζήτηση σε πίνακα 100 στοιχείων, και πόσα σε 200;

1. **Για $100$:** $2^6 = 64 \le 100 < 128 = 2^7$, άρα $\lfloor \log_2 100 \rfloor = 6$ και η χειρότερη περίπτωση είναι $7$.
2. **Για $200$:** $128 \le 200 < 256$, άρα $8$. Ο διπλασιασμός πρόσθεσε μία επανάληψη.
3. **Η σειριακή** θα χρειαζόταν στη χειρότερη περίπτωση $100$ και $200$. Στον πίνακα $1, 2, \dots, 100$, το $73$ βρίσκεται σε $6$ επαναλήψεις, με μέσες $50, 75, 62, 68, 71, 73$.

### Παράδειγμα 4: Θέμα Β. Στο τμήμα κώδικα της δυαδικής αναζήτησης λείπουν πέντε εκφράσεις, γραμμένες κενό\_1 ως κενό\_5. Να γράψεις τι μπαίνει στο καθένα.

1. *Διαδραστικό στη σελίδα: Το τμήμα με τα κενά*
2. **Κενό 1:** `n`, το τέλος του πίνακα. **Κενό 2:** `ΨΕΥΔΗΣ`, ο βρόχος συνεχίζει όσο δεν έχει βρεθεί.
3. **Κενό 3:** `mid - 1`, το `key` είναι αριστερά. **Κενό 4:** `mid + 1`, δεξιά. **Κενό 5:** `ΑΛΗΘΗΣ`.
4. **Ο έλεγχος της απάντησης:** εκτέλεσε το συμπληρωμένο τμήμα για ένα `key` που υπάρχει και για ένα που λείπει. Αν τελειώνει και στις δύο περιπτώσεις, τα κενά 3 και 4 είναι σωστά.

### Παράδειγμα 5: Ο πίνακας Β έχει σε φθίνουσα σειρά τις τιμές 52, 46, 41, 34, 30, 27, 21, 15, 12, 8, 3. Να εκτελέσεις τη δυαδική αναζήτηση για key = 15.

1. **Η αλλαγή:** τώρα `key > B[mid]` σημαίνει «αριστερά», άρα `last ← mid − 1`, και `key < B[mid]` σημαίνει «δεξιά».
2. **`mid = 6`**, $B[6] = 27$, $15 < 27$, `first ← 7`. **`mid = 9`**, $B[9] = 12$, $15 > 12$, `last ← 8`.
3. **`mid = 7`**, $B[7] = 21$, $15 < 21$, `first ← 8`. **`mid = 8`**, $B[8] = 15$: βρέθηκε στη θέση $8$, μετά από τέσσερις επαναλήψεις.

### Παράδειγμα 6: Θέμα Δ. Ο πίνακας ΚΩΔ έχει τους κωδικούς 7 προϊόντων σε αύξουσα σειρά και ο ΤΙΜ τις τιμές τους, στις ίδιες θέσεις. Να γράψεις τμήμα που διαβάζει κωδικούς μέχρι να δοθεί 0 και τυπώνει για τον καθένα την τιμή του ή «δεν υπάρχει».

1. **Ο εξωτερικός βρόχος** είναι `ΟΣΟ`, με ανάγνωση πριν από αυτόν και στο τέλος του σώματος: το $0$ μπορεί να δοθεί πρώτο.
2. **Η αναζήτηση γίνεται στον ΚΩΔ**, και τα `first`, `last`, `done` αρχικοποιούνται **μέσα** στον εξωτερικό βρόχο, ξανά για κάθε κωδικό.
3. **Η τιμή βγαίνει από τον παράλληλο πίνακα**, στη θέση `mid` όπου βρέθηκε ο κωδικός.

   *Διαδραστικό στη σελίδα: Τιμή προϊόντος από τον κωδικό του*
4. **Έξοδος:** `138 7.8`, `120 δεν υπάρχει`, `171 6`. Το λάθος που κοστίζει εδώ είναι οι αρχικοποιήσεις έξω από τον εξωτερικό βρόχο: η δεύτερη αναζήτηση θα ξεκινούσε με τα `first` και `last` της πρώτης.

## Ερωτήσεις

1. Πριν τρέξεις τη δυαδική αναζήτηση σε έναν πίνακα, τι πρέπει να έχεις εξασφαλίσει;
   - ότι είναι ταξινομημένος
   - ότι είναι μονοδιάστατος
   - ότι δεν έχει διπλότυπα
   - ότι έχει μέγεθος $2^k$
2. Με `first = 4` και `last = 9`, ποια τιμή παίρνει το `mid`;
   - $6$
   - $6{,}5$
   - $7$
   - $2$
3. Σε αύξουσα σειρά ισχύει `key < A[mid]`. Ποια εντολή εκτελείται;
   - `last <- mid - 1`
   - `first <- mid + 1`
   - `last <- mid`
   - `first <- mid - 1`
4. Πότε σταματά ο βρόχος αν το `key` δεν υπάρχει στον πίνακα;
   - όταν το `first` γίνει μεγαλύτερο από το `last`
   - όταν το `mid` φτάσει στο `n`
   - όταν το `first` γίνει ίσο με το `last`
   - μετά από $n$ επαναλήψεις του βρόχου
5. Πόσα στοιχεία εξετάζει στη χειρότερη περίπτωση η δυαδική σε ταξινομημένο πίνακα $1000$ στοιχείων;
   - $10$
   - $500$
   - $1000$
   - $9$
6. Ένας ταξινομημένος πίνακας διπλασιάζεται, από $500$ σε $1000$ στοιχεία. Η χειρότερη περίπτωση της δυαδικής:
   - αυξάνεται κατά μία επανάληψη
   - διπλασιάζεται, όπως ο πίνακας
   - μένει ακριβώς η ίδια
   - τετραπλασιάζεται, όπως στη φυσαλίδα
7. Γιατί γράφεται `first <- mid + 1` και όχι `first <- mid`;
   - για να μη μείνει ο βρόχος κολλημένος στο ίδιο διάστημα
   - για να ξεκινά πάντα η μέτρηση από τη θέση $1$
   - γιατί το `mid` είναι πάντα δεκαδικός αριθμός
   - για να εξεταστεί η μέση άλλη μία φορά
8. Ο πίνακας είναι σε φθίνουσα σειρά. Τι αλλάζεις στη δυαδική αναζήτηση του βιβλίου;
   - αντιστρέφεις τις δύο συγκρίσεις `<` και `>`
   - ξεκινάς με `first <- n` και `last <- 1`
   - γράφεις `mid <- (first - last) DIV 2`
   - τίποτα, δουλεύει όπως είναι ήδη
9. Ποια είναι η καλύτερη περίπτωση της δυαδικής αναζήτησης σε πίνακα $n$ στοιχείων;
   - ένα εξεταζόμενο στοιχείο
   - $n / 2$ εξεταζόμενα στοιχεία
   - $\lfloor \log_2 n \rfloor + 1$ στοιχεία
   - μηδέν εξεταζόμενα στοιχεία
10. Μετά τον βρόχο, από τι καταλαβαίνεις αν βρέθηκε το `key`;
   - από την τιμή της σημαίας `done`
   - από το αν το `mid` έχει τιμή
   - από το αν ισχύει `first = last`
   - από το αν ισχύει `mid = n`

## Ασκήσεις

1. Πίνακας $20$ στοιχείων: με `first = 1` και `last = 20`, ποια τιμή παίρνει το `mid` στην πρώτη επανάληψη;
2. Πόσα στοιχεία εξετάζει στη χειρότερη περίπτωση η δυαδική αναζήτηση σε ταξινομημένο πίνακα $31$ στοιχείων;
3. Ο πίνακας Α έχει $20$ στοιχεία με `Α[i] = 5 * i`, δηλαδή $5, 10, \dots, 100$. Πόσα στοιχεία εξετάζει η δυαδική αναζήτηση του βιβλίου για `key = 65`;
4. Πόσα στοιχεία εξετάζει στη χειρότερη περίπτωση η δυαδική αναζήτηση σε ταξινομημένο πίνακα $500$ στοιχείων;
5. Ο ταξινομημένος πίνακας Β έχει $15$ στοιχεία: $2, 5, 8, 11, \dots, 44$, το καθένα κατά $3$ μεγαλύτερο από το προηγούμενο. Εκτελείται η δυαδική αναζήτηση του βιβλίου για `key = 30`, που δεν υπάρχει.
   α) Ποιο στοιχείο εξετάζεται πρώτο;
   β) Πόσα στοιχεία εξετάζονται συνολικά;
   γ) Ποιες είναι οι τελικές τιμές των `first` και `last`;
6. Ο πίνακας Δ έχει σε φθίνουσα σειρά τις τιμές $52, 46, 41, 34, 30, 27, 21, 15, 12, 8, 3$. Εκτελείται η δυαδική αναζήτηση προσαρμοσμένη για φθίνουσα σειρά.
   α) Πόσα στοιχεία εξετάζονται για `key = 46`;
   β) Ποια είναι η τιμή του `position` για `key = 46`;
   γ) Πόσα στοιχεία εξετάζονται για `key = 9`, που λείπει;
7. Στη δυαδική αναζήτηση του βιβλίου κάποιος έγραψε `last <- mid` αντί για `last <- mid - 1`. Ο πίνακας είναι $3, 8, 12, 15, 21, 27, 30, 34, 41, 46, 52$.
   α) Πόσα στοιχεία εξετάζονται για `key = 34`;
   β) Για `key = 10`, σε ποιες τιμές των `first` και `last` κολλάει ο βρόχος;
   γ) Τι είδους λάθος είναι αυτό;
8. Ο ΚΩΔ έχει τους κωδικούς $104, 117, 125, 138, 142, 156, 171$ και ο ΤΙΜ τις τιμές $2.5, 4, 1.2, 7.8, 3, 12.5, 6$. Το τμήμα του Θέματος Δ του μαθήματος διαβάζει τους κωδικούς $125$, $150$ και μετά $0$.
   α) Τι τυπώνει για τον κωδικό $125$;
   β) Πόσα στοιχεία του ΚΩΔ εξετάζονται για τον $150$;
   γ) Αν τα `first <- 1`, `last <- n`, `done <- ΨΕΥΔΗΣ` μπουν πριν από τον εξωτερικό βρόχο, τι τυπώνει για τον $150$;

---

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