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

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

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

40 λεπτά

Στο σχολικό βιβλίο: Ανάπτυξη Εφαρμογών σε Προγραμματιστικό Περιβάλλον Γ΄ Λυκείου, 1 ενότητα

Στις Πανελλήνιες2025 Α ·2022 επαν. Α ·2021 Α

Θα μάθεις να

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

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

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

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

Ο πίνακας έχει 11 ταξινομημένες τιμές: 3, 8, 12, 15, 21, 27, 30, 34, 41, 46, 52. Πριν από κάθε βήμα πες τη νέα τιμή του mid, ή ποιο από τα first και last θα αλλάξει.

  1. τρέχουσα γραμμή: first ← 1
  2. last ← n
  3. done ← ΨΕΥΔΗΣ
  4. position ← 0
  5. ΟΣΟ first <= last ΚΑΙ done = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ
  6. mid ← (first + last) DIV 2
  7. ΑΝ key < A[mid] ΤΟΤΕ
  8. last ← mid - 1
  9. ΑΛΛΙΩΣ_ΑΝ key > A[mid] ΤΟΤΕ
  10. first ← mid + 1
  11. ΑΛΛΙΩΣ
  12. done ← ΑΛΗΘΗΣ
  13. position ← mid
  14. ΤΕΛΟΣ_ΑΝ
  15. ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ

Ξεκινάμε με A = [3, 8, 12, 15, 21, 27, 30, 34, 41, 46, 52], n = 11, key = 34.Γραμμή 1: τι τιμή θα πάρει το first;

Μεταβλητές

A
= [3, 8, 12, 15, 21, 27, 30, 34, 41, 46, 52]
n
= 11
key
= 34

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

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

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

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

Τα first, last και mid για το 34

Η στήλη «Αλλάζει» είναι η απόφαση της επανάληψης. Βγαίνει από τη σύγκριση της ίδιας γραμμής.

ΒήμαfirstlastmidA[mid]ΣύγκρισηΑλλάζει
Ζωντανή ενημέρωση

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

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

Αναζήτηση του 10, που λείπει

Πρόσεξε τι γίνεται μετά την τέταρτη γραμμή: το first ξεπερνά το last και ο βρόχος σταματά χωρίς να βρει τίποτα.

ΒήμαfirstlastmidA[mid]ΣύγκρισηΑλλάζει
Ζωντανή ενημέρωση

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

Το μήνυμα μετά την αναζήτηση
  1. ΑΝ done = ΑΛΗΘΗΣ ΤΟΤΕ
  2. ΓΡΑΨΕ 'Βρέθηκε στη θέση', position
  3. ΑΛΛΙΩΣ
  4. ΓΡΑΨΕ 'Δεν βρέθηκε'
  5. ΤΕΛΟΣ_ΑΝ

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

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

⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1

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

nn7788151516161001001000100010241024
χειρότερη περίπτωση334444557710101111

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

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

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

Δυαδική σε φθίνουσα σειρά
  1. σημειωμένη γραμμή: ΑΝ key > A[mid] ΤΟΤΕ
  2. last ← mid - 1
  3. σημειωμένη γραμμή: ΑΛΛΙΩΣ_ΑΝ key < A[mid] ΤΟΤΕ
  4. first ← mid + 1
  5. ΑΛΛΙΩΣ
  6. done ← ΑΛΗΘΗΣ
  7. position ← mid
  8. ΤΕΛΟΣ_ΑΝ

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

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

Παράδειγμα 1

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

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 2

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

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 3

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

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 4

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

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 5

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

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Παράδειγμα 6

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

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Πολλαπλή επιλογή

Πολλαπλή επιλογήΆσκηση 1 από 10
Πριν τρέξεις τη δυαδική αναζήτηση σε έναν πίνακα, τι πρέπει να έχεις εξασφαλίσει;

Ασκήσεις

ΒασικήΆσκηση 1 από 8

Πίνακας 2020 στοιχείων: με first = 1 και last = 20, ποια τιμή παίρνει το mid στην πρώτη επανάληψη;

Τα κατάφερες;

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

Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.

Βρήκες κάποιο λάθος;