Ως γνωστόν η δυαδική αναζήτηση είναι μια μέθοδος που εφαρμόζεται
σε ταξινομημένους πίνακες. Η μέθοδος λειτουργεί ως εξής:
α) Υπάρχουν δύο δείκτες ΑΡΧ και ΤΕΛ που προσδιορίζουν το εύρος
του διαστήματος μέσα στο οποίο κάνουμε την αναζήτηση
(αρχικά ΑΡΧ = 1 και ΤΕΛ = 100)
β) Υπολογίζουμε το μέσο Μ του διαστήματος [ΑΡΧ, ΤΕΛ]
γ) Αν Α[Μ] = Χ, τότε το στοιχείο εντοπίστηκε στη θέση Μ και η
μέθοδος ολοκληρώθηκε.
δ) Αν Α[Μ] < Χ, η αναζήτηση συνεχίζεται στο διάστημα [Μ+1, ΤΕΛ]
ε) Αν Α[Μ] > Χ, η αναζήτηση συνεχίζεται στο διάστημα [ΑΡΧ, Μ-1]
στ) Αν κατά την εκτέλεση της μεθόδου, το ΑΡΧ γίνει μεγαλύτερο του
ΤΕΛ, είμαστε σίγουροι ότι η τιμή Χ δεν υπάρχει μέσα στον πίνακα
και η αναζήτηση σταματά επί τόπου.
Γράψτε διαδικασία που να υλοποιεί την παραπάνω μέθοδο.
Λύση
ΔΙΑΔΙΚΑΣΙΑ ΔΥΑΔΙΚΗ(Α, Χ, ΒΡΕΘ, ΘΕΣΗ)
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α[200], Χ, ΑΡΧ, ΤΕΛ, Μ
ΛΟΓΙΚΕΣ : ΒΡΕΘ
ΑΡΧΗ
ΒΡΕΘ <-- ΨΕΥΔΗΣ
ΑΡΧ <-- 1
ΤΕΛ <-- 200
Μ <-- (ΑΡΧ+ΤΕΛ) DIV 2
ΘΕΣΗ <-- 0
ΟΣΟ (ΑΡΧ <= ΤΕΛ) ΚΑΙ (ΒΡΕΘ = ΨΕΥΔΗΣ) ΕΠΑΝΑΛΑΒΕ
ΑΝ Α[Μ] = Χ ΤΟΤΕ
ΒΡΕΘ <-- ΑΛΗΘΗΣ
ΘΕΣΗ <-- Μ
ΑΛΛΙΩΣ_ΑΝ Α[Μ] < Χ ΤΟΤΕ
ΑΡΧ <-- Μ+1
ΑΛΛΙΩΣ ! A[M] > X
ΤΕΛ <-- Μ-1
ΤΕΛΟΣ_ΑΝ
Μ <-- (ΑΡΧ+ΤΕΛ) DIV 2
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
σε ταξινομημένους πίνακες. Η μέθοδος λειτουργεί ως εξής:
α) Υπάρχουν δύο δείκτες ΑΡΧ και ΤΕΛ που προσδιορίζουν το εύρος
του διαστήματος μέσα στο οποίο κάνουμε την αναζήτηση
(αρχικά ΑΡΧ = 1 και ΤΕΛ = 100)
β) Υπολογίζουμε το μέσο Μ του διαστήματος [ΑΡΧ, ΤΕΛ]
γ) Αν Α[Μ] = Χ, τότε το στοιχείο εντοπίστηκε στη θέση Μ και η
μέθοδος ολοκληρώθηκε.
δ) Αν Α[Μ] < Χ, η αναζήτηση συνεχίζεται στο διάστημα [Μ+1, ΤΕΛ]
ε) Αν Α[Μ] > Χ, η αναζήτηση συνεχίζεται στο διάστημα [ΑΡΧ, Μ-1]
στ) Αν κατά την εκτέλεση της μεθόδου, το ΑΡΧ γίνει μεγαλύτερο του
ΤΕΛ, είμαστε σίγουροι ότι η τιμή Χ δεν υπάρχει μέσα στον πίνακα
και η αναζήτηση σταματά επί τόπου.
Γράψτε διαδικασία που να υλοποιεί την παραπάνω μέθοδο.
Λύση
ΔΙΑΔΙΚΑΣΙΑ ΔΥΑΔΙΚΗ(Α, Χ, ΒΡΕΘ, ΘΕΣΗ)
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α[200], Χ, ΑΡΧ, ΤΕΛ, Μ
ΛΟΓΙΚΕΣ : ΒΡΕΘ
ΑΡΧΗ
ΒΡΕΘ <-- ΨΕΥΔΗΣ
ΑΡΧ <-- 1
ΤΕΛ <-- 200
Μ <-- (ΑΡΧ+ΤΕΛ) DIV 2
ΘΕΣΗ <-- 0
ΟΣΟ (ΑΡΧ <= ΤΕΛ) ΚΑΙ (ΒΡΕΘ = ΨΕΥΔΗΣ) ΕΠΑΝΑΛΑΒΕ
ΑΝ Α[Μ] = Χ ΤΟΤΕ
ΒΡΕΘ <-- ΑΛΗΘΗΣ
ΘΕΣΗ <-- Μ
ΑΛΛΙΩΣ_ΑΝ Α[Μ] < Χ ΤΟΤΕ
ΑΡΧ <-- Μ+1
ΑΛΛΙΩΣ ! A[M] > X
ΤΕΛ <-- Μ-1
ΤΕΛΟΣ_ΑΝ
Μ <-- (ΑΡΧ+ΤΕΛ) DIV 2
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου