Παρασκευή, 23 Μαρτίου 2012

Δυαδική αναζήτηση του ακέραιου Χ στον ακέραιο ταξινομημένο πίνακα Α[200]

Ως γνωστόν η δυαδική αναζήτηση είναι μια μέθοδος που εφαρμόζεται
σε ταξινομημένους πίνακες. Η μέθοδος λειτουργεί ως εξής:
α) Υπάρχουν δύο δείκτες ΑΡΧ και ΤΕΛ που προσδιορίζουν το εύρος
    του διαστήματος μέσα στο οποίο κάνουμε την αναζήτηση
    (αρχικά ΑΡΧ = 1 και ΤΕΛ =  100)
β) Υπολογίζουμε το μέσο Μ του διαστήματος [ΑΡΧ, ΤΕΛ]
γ) Αν Α[Μ] = Χ, τότε το στοιχείο εντοπίστηκε στη θέση Μ και η
    μέθοδος ολοκληρώθηκε.
δ) Αν Α[Μ] < Χ, η αναζήτηση συνεχίζεται στο διάστημα [Μ+1, ΤΕΛ]
ε) Αν Α[Μ] > Χ, η αναζήτηση συνεχίζεται στο διάστημα [ΑΡΧ, Μ-1]
στ) Αν κατά την εκτέλεση της μεθόδου, το ΑΡΧ γίνει μεγαλύτερο του
      ΤΕΛ, είμαστε σίγουροι ότι η τιμή Χ δεν υπάρχει μέσα στον πίνακα
       και η αναζήτηση σταματά επί τόπου.
Γράψτε διαδικασία που να υλοποιεί την παραπάνω μέθοδο.

Λύση

      ΔΙΑΔΙΚΑΣΙΑ ΔΥΑΔΙΚΗ(Α, Χ, ΒΡΕΘ, ΘΕΣΗ)
      ΜΕΤΑΒΛΗΤΕΣ
             ΑΚΕΡΑΙΕΣ: Α[200], Χ, ΑΡΧ, ΤΕΛ, Μ
             ΛΟΓΙΚΕΣ : ΒΡΕΘ
      ΑΡΧΗ
             ΒΡΕΘ <-- ΨΕΥΔΗΣ
             ΑΡΧ <-- 1
             ΤΕΛ <-- 200
             Μ <-- (ΑΡΧ+ΤΕΛ) DIV 2
             ΘΕΣΗ <-- 0
             ΟΣΟ (ΑΡΧ <= ΤΕΛ) ΚΑΙ (ΒΡΕΘ = ΨΕΥΔΗΣ) ΕΠΑΝΑΛΑΒΕ
                     ΑΝ Α[Μ] = Χ ΤΟΤΕ
                           ΒΡΕΘ <-- ΑΛΗΘΗΣ
                           ΘΕΣΗ <-- Μ
                     ΑΛΛΙΩΣ_ΑΝ Α[Μ] < Χ ΤΟΤΕ
                           ΑΡΧ <-- Μ+1
                     ΑΛΛΙΩΣ  ! A[M] > X
                           ΤΕΛ <-- Μ-1
                     ΤΕΛΟΣ_ΑΝ
                     Μ <-- (ΑΡΧ+ΤΕΛ) DIV 2
              ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
      ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου