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

ΝΕΑ

Έστω ότι δίνεται ένας ηλεκτρονικός τηλεφωνικός κατάλογος, δηλαδή ένας πίνακας με n ονόματα και έναν αριθμό τηλεφώνου για κάθε όνομα. Ο κατάλογος είναι ταξινομημένος κατά αύξουσα αλφαβητική τάξη ως προς τα ονόματα. Έστω ότι τα n ονόματα με τα αντίστοιχα τηλέφωνα είναι αποθηκευμένα σε δύο πίνακες: names[1 ..n] και phones[1 ..n] αντίστοιχα. Σε μία τέτοια περίπτωση, λοιπόν, το ζητούμενο είναι να βρεθεί το τηλέφωνο που αντιστοιχεί σε δεδομένο όνομα συνδρομητή (υποθέτοντας ότι το δεδομένο αναζητούμενο όνομα πράγματι υπάρχει στον κατάλογο).Το πρόβλημα επιλύεται με τη μέθοδο Διαίρει και Βασίλευε με βάση την παρατήρηση ότι όταν δοθεί ένα όνομα, τότε υπάρχουν οι εξής 3 περιπτώσεις:

1. το όνομα βρίσκεται στη μεσαία θέση του πίνακα names,
2. το όνομα βρίσκεται σε μία θέση στο πρώτο μισό κομμάτι του πίνακα names, ή
3. το όνομα βρίσκεται σε μία θέση στο δεύτερο μισό κομμάτι του πίνακα names.

Η παρατήρηση αυτή οδηγεί στη σύνταξη του επόμενου αλγορίθμου. Σημειώνεται ότι ο αλγόριθμος αυτός ισχύει μόνο για την περίπτωση που το αναζητούμενο όνομα υπάρχει στον κατάλογο (δηλαδή, στον πίνακα names). Ο αλγόριθμος αυτός μπορεί εύκολα να τροποποιηθεί ώστε να αντιμετωπίζει και την περίπτωση της “ανεπιτυχούς αναζήτησης”, δηλαδής της περίπτωσης όπου το αναζητούμενο όνομα δεν υπάρχει στον πίνακα.

! Αλγόριθμος επεξήγησης (αναδρομικός - εκτός ύλης), βλέπε παρακάτω το πρόγραμμα 
Αλγόριθμος Δυαδική_αναζήτηση
Δεδομένα  //names, phones, onoma, arhi, telos // ! παρόραμα arxi
meso <-- [arhi + telos] / 2
Αν onoma = names[meso] τότε
   Tel <-- phones[meso]
Αλλιώς
   Αν onoma < names[meso] τότε
      Δυαδική_αναζήτηση(names, phones, onoma, arhi, meso-1)
   αλλιώς
      Δυαδική αναζήτηση(names, phones, onoma, meso+1, telos)
   Τέλος_αν
Τέλος_αν
Αποτελέσματα // Tel //
Τέλος Δυαδική_αναζήτηση

Παρατήρηση: Η δυαδική αναζήτηση χρησιμοποιείται μόνο στην περίπτωση ταξινομημένου πίνακα.

Παράδειγμα. Το παράδειγμα που ακολουθεί παρακολουθεί την αλληλουχία των βημάτων του αλγορίθμου της δυαδικής αναζήτησης ενός ονόματος σε έναν πίνακα πέντε θέσεων. Έστω ότι στον τηλεφωνικό κατάλογο αναζητείται το όνομα Δανάη. Κατά την πρώτη προσπάθεια από τις πέντε

Σχ. 4.3 Διαδοχικές συγκρίσεις σε αρχικό πίνακα και υπο-πίνακες για την αναζήτηση του ονόματος Δανάη.

θέσεις ελέγχεται η μεσαία, δηλαδή η τρίτη, όπου βρίσκεται το όνομα Κατερίνα. Το όνομα Δανάη είναι λεξικογραφικά μικρότερο από το όνομα Κατερίνα και επομένως η αναζήτηση περιορίζεται στο πρώτο μισό του πίνακα που αποτελείται από δυο θέσεις. Από τις δύο αυτές θέσεις, σε μία δεύτερη προσπάθεια ελέγχεται η πρώτη θέση, όπου βρίσκεται το τηλέφωνο του Γιάννη. Επειδή, το όνομα Δανάη είναι λεξικογραφικά μεγαλύτερο από το όνομα Γιάννης, η αναζήτηση περιορίζεται στον υπο-πίνακα που αποτελείται από τη δεύτερη θέση μόνο. Έτσι, στη θέση αυτή με μία τρίτη προσπάθεια βρίσκουμε το τηλέφωνο της Δανάης.

! ΟΔΗΓΙΕΣ ΔΙΔΑΣΚΑΛΙΑΣ 2016-2017, Παράρτημα Γ
! Αναζήτηση σε ΤΑΞΙΝΟΜΕΝΟ πίνακα 20 θέσεων
ΠΡΟΓΡΑΜΜΑ δυαδική_αναζήτηση 
ΜΕΤΑΒΛΗΤΕΣ 
ΑΚΕΡΑΙΕΣ: A[20], Left, Right, M, k, S, i 
ΛΟΓΙΚΕΣ: found 
ΑΡΧΗ 
ΓΡΑΨΕ 'Οι αριθμοί που θα δοθούν πρέπει να είναι ταξινομημένοι κατά αύξουσα τάξη' 
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ 20 
    ΓΡΑΨΕ 'Δώσε το', i, ' στοιχείο του πίνακα' 
    ΔΙΑΒΑΣΕ A[i] 
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ 
ΓΡΑΨΕ 'Δωσε τιμή για αναζήτηση: ' 
ΔΙΑΒΑΣΕ S 
Left <-- 1 
Right <-- 20 
k <-- 0 
found <-- ΨΕΥΔΗΣ 
ΟΣΟ (Left <= Right) ΚΑΙ (found = ΨΕΥΔΗΣ) ΕΠΑΝΑΛΑΒΕ 
     M <-- (Left + Right) DIV 2 
     ΑΝ A[M] = S ΤΟΤΕ 
        k <-- M 
        found <-- ΑΛΗΘΗΣ 
    ΑΛΛΙΩΣ 
       ΑΝ A[M] < S ΤΟΤΕ 
          Left <-- M + 1 
       ΑΛΛΙΩΣ 
          Right <-- M - 1 
       ΤΕΛΟΣ_ΑΝ 
    ΤΕΛΟΣ_ΑΝ 
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ 
ΑΝ found = ΑΛΗΘΗΣ ΤΟΤΕ 
   ΓΡΑΨΕ 'Το στοιχείο,', S, 'υπάρχει στη θέση:', M 
ΑΛΛΙΩΣ 
   ΓΡΑΨΕ 'Το στοιχείο,', S, ' δεν υπάρχει στον πίνακα'
ΤΕΛΟΣ_ΑΝ 
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ δυαδική_αναζήτηση

*Ως άσκηση μπορεί να δοθεί η βελτιστοποίηση του αλγορίθμου δυαδικής αναζήτησης έτσι ώστε να επιτρέπει διαδοχικές αναζητήσεις πολλών στοιχείων. Η αναζήτηση να τερματίζεται όταν δοθεί κάποιος συγκεκριμένος αριθμός ή με ερώτηση “Θέλετε άλλη αναζήτηση (Ν/Ο)”