Δυαδική αναζήτηση βήμα βήμα
Ο πίνακας τιμών των first, last και mid, το «δεν βρέθηκε», και πόσες συγκρίσεις χρειάζονται.
40 λεπτά
Στο σχολικό βιβλίο: Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον Γ΄ Λυκείου, 1 ενότητα
Στις Πανελλήνιες2025 Α ·2022 επαν. Α ·2021 Α
Θα μάθεις να
- Να εκτελείς τη δυαδική αναζήτηση του βιβλίου με πίνακα τιμών για τα first, last και mid.
- Να μετράς πόσα στοιχεία εξετάζονται, και τη χειρότερη περίπτωση για πίνακα n στοιχείων.
- Να προσαρμόζεις τον αλγόριθμο σε φθίνουσα σειρά και να συμπληρώνεις τα κενά του.
- Να τον χρησιμοποιείς σε πρόγραμμα με παράλληλους πίνακες.
Ο αλγόριθμος του βιβλίου
Η δυαδική αναζήτηση δουλεύει μόνο σε ταξινομημένο πίνακα. Κρατά δύο δείκτες, το first και το last, για το κομμάτι όπου μπορεί ακόμα να βρίσκεται το ζητούμενο key. Σε κάθε επανάληψη κοιτάζει τη μέση mid και πετά το μισό που αποκλείεται.
Κάθε γραμμή έχει λόγο ύπαρξης:
- Η γραμμή 6 βρίσκει τη μέση με ακέραια διαίρεση. Το
DIVκόβει το δεκαδικό: γιαfirst = 7,last = 8δίνειmid = 7. - Οι γραμμές 8 και 10 μετακινούν το όριο μία θέση πέρα από τη μέση. Η μέση έχει ήδη εξεταστεί, δεν χρειάζεται να μείνει μέσα.
- Η σημαία
doneσταματά τον βρόχο μόλις βρεθεί το στοιχείο. Τοfirst <= lastτον σταματά όταν το διάστημα αδειάσει.
Βήμα βήμα, με πίνακα τιμών
Ο ίδιος πίνακας, το ίδιο key = 34. Πες τι θα αλλάξει πριν πατήσεις.
Όταν το στοιχείο δεν υπάρχει
Τώρα ψάχνεις το , που δεν είναι στον πίνακα.
Μετά τον βρόχο, η απάντηση βγαίνει από τη σημαία:
ΑΝ done = ΑΛΗΘΗΣ ΤΟΤΕΓΡΑΨΕ 'Βρέθηκε στη θέση', positionΑΛΛΙΩΣΓΡΑΨΕ 'Δεν βρέθηκε'ΤΕΛΟΣ_ΑΝ
Πόσα στοιχεία εξετάζονται
Κάθε επανάληψη εξετάζει ένα στοιχείο, το A[mid], και κρατά το πολύ το μισό διάστημα. Για πίνακα στοιχείων, η χειρότερη περίπτωση είναι
επαναλήψεις. Στην πράξη το βρίσκεις χωρίς λογάριθμο: η μικρότερη δύναμη του που ξεπερνά το είναι , και η απάντηση είναι .
| χειρότερη περίπτωση |
Η καλύτερη περίπτωση είναι μία επανάληψη: το key είναι ακριβώς στη μέση.
Φθίνουσα σειρά
Αν ο πίνακας είναι ταξινομημένος από το μεγαλύτερο στο μικρότερο, οι μικρότερες τιμές είναι δεξιά. Άρα αντιστρέφονται οι δύο συγκρίσεις:
- σημειωμένη γραμμή:
ΑΝ key > A[mid] ΤΟΤΕ last ← mid - 1- σημειωμένη γραμμή:
ΑΛΛΙΩΣ_ΑΝ key < A[mid] ΤΟΤΕ first ← mid + 1ΑΛΛΙΩΣdone ← ΑΛΗΘΗΣposition ← midΤΕΛΟΣ_ΑΝ
Οι αναθέσεις στα first και last μένουν ίδιες. Αλλάζει μόνο το πότε γίνεται η καθεμιά.
Παραδείγματα
Παράδειγμα 1
Θέμα Β. Ο πίνακας Α έχει τις τιμές 7, 11, 16, 20, 25, 31, 38, 44, 50. Να γράψεις τον πίνακα τιμών της δυαδικής αναζήτησης για key = 16, και την τελική τιμή του position.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Τρεις επαναλήψεις,
position = 3. Στη δεύτερη γραμμή, : το δεκαδικό κόβεται, δεν στρογγυλεύεται.
Παράδειγμα 2
Στον ίδιο πίνακα 7, 11, 16, 20, 25, 31, 38, 44, 50 ψάχνεις το 45. Πόσα στοιχεία εξετάζονται, και με ποιες τιμές των first και last τελειώνει ο βρόχος;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Πρώτη επανάληψη:
mid = 5, ,first ← 6. Δεύτερη:mid = (6 + 9) DIV 2 = 7, ,first ← 8.Τρίτη:
mid = 8, ,first ← 9. Τέταρτη:mid = 9, ,last ← 8.Τέσσερα στοιχεία: . Ο βρόχος τελειώνει με
first = 9καιlast = 8, και η σημαίαΨΕΥΔΗΣ. Το θα έμπαινε στη θέση , ανάμεσα στο και στο .
Παράδειγμα 3
Πόσα στοιχεία εξετάζει στη χειρότερη περίπτωση η δυαδική αναζήτηση σε πίνακα 100 στοιχείων, και πόσα σε 200;
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Για : , άρα και η χειρότερη περίπτωση είναι .
Για : , άρα . Ο διπλασιασμός πρόσθεσε μία επανάληψη.
Η σειριακή θα χρειαζόταν στη χειρότερη περίπτωση και . Στον πίνακα , το βρίσκεται σε επαναλήψεις, με μέσες .
Παράδειγμα 4
Θέμα Β. Στο τμήμα κώδικα της δυαδικής αναζήτησης λείπουν πέντε εκφράσεις, γραμμένες κενό_1 ως κενό_5. Να γράψεις τι μπαίνει στο καθένα.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Το τμήμα με τα κενά first ← 1- σημειωμένη γραμμή:
last ← κενό_1 done ← ΨΕΥΔΗΣ- σημειωμένη γραμμή:
ΟΣΟ first <= last ΚΑΙ done = κενό_2 ΕΠΑΝΑΛΑΒΕ mid ← (first + last) DIV 2ΑΝ key < A[mid] ΤΟΤΕ- σημειωμένη γραμμή:
last ← κενό_3 ΑΛΛΙΩΣ_ΑΝ key > A[mid] ΤΟΤΕ- σημειωμένη γραμμή:
first ← κενό_4 ΑΛΛΙΩΣ- σημειωμένη γραμμή:
done ← κενό_5 ΤΕΛΟΣ_ΑΝΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Κενό 1:
n, το τέλος του πίνακα. Κενό 2:ΨΕΥΔΗΣ, ο βρόχος συνεχίζει όσο δεν έχει βρεθεί.Κενό 3:
mid - 1, τοkeyείναι αριστερά. Κενό 4:mid + 1, δεξιά. Κενό 5:ΑΛΗΘΗΣ.Ο έλεγχος της απάντησης: εκτέλεσε το συμπληρωμένο τμήμα για ένα
keyπου υπάρχει και για ένα που λείπει. Αν τελειώνει και στις δύο περιπτώσεις, τα κενά 3 και 4 είναι σωστά.
Παράδειγμα 5
Ο πίνακας Β έχει σε φθίνουσα σειρά τις τιμές 52, 46, 41, 34, 30, 27, 21, 15, 12, 8, 3. Να εκτελέσεις τη δυαδική αναζήτηση για key = 15.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Η αλλαγή: τώρα
key > B[mid]σημαίνει «αριστερά», άραlast ← mid − 1, καιkey < B[mid]σημαίνει «δεξιά».mid = 6, , ,first ← 7.mid = 9, , ,last ← 8.mid = 7, , ,first ← 8.mid = 8, : βρέθηκε στη θέση , μετά από τέσσερις επαναλήψεις.
Παράδειγμα 6
Θέμα Δ. Ο πίνακας ΚΩΔ έχει τους κωδικούς 7 προϊόντων σε αύξουσα σειρά και ο ΤΙΜ τις τιμές τους, στις ίδιες θέσεις. Να γράψεις τμήμα που διαβάζει κωδικούς μέχρι να δοθεί 0 και τυπώνει για τον καθένα την τιμή του ή «δεν υπάρχει».
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
Ο εξωτερικός βρόχος είναι
ΟΣΟ, με ανάγνωση πριν από αυτόν και στο τέλος του σώματος: το μπορεί να δοθεί πρώτο.Η αναζήτηση γίνεται στον ΚΩΔ, και τα
first,last,doneαρχικοποιούνται μέσα στον εξωτερικό βρόχο, ξανά για κάθε κωδικό.Η τιμή βγαίνει από τον παράλληλο πίνακα, στη θέση
midόπου βρέθηκε ο κωδικός.Έξοδος:
138 7.8,120 δεν υπάρχει,171 6. Το λάθος που κοστίζει εδώ είναι οι αρχικοποιήσεις έξω από τον εξωτερικό βρόχο: η δεύτερη αναζήτηση θα ξεκινούσε με ταfirstκαιlastτης πρώτης.
Πολλαπλή επιλογή
Ασκήσεις
Πίνακας στοιχείων: με first = 1 και last = 20, ποια τιμή παίρνει το mid στην πρώτη επανάληψη;
Τα κατάφερες;
- Να εκτελείς τη δυαδική αναζήτηση του βιβλίου με πίνακα τιμών για τα first, last και mid.
- Να μετράς πόσα στοιχεία εξετάζονται, και τη χειρότερη περίπτωση για πίνακα n στοιχείων.
- Να προσαρμόζεις τον αλγόριθμο σε φθίνουσα σειρά και να συμπληρώνεις τα κενά του.
- Να τον χρησιμοποιείς σε πρόγραμμα με παράλληλους πίνακες.
Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.