Δυαδική Αναζήτηση
Και μια ακόμη πρόταση για γρήγορη αναζήτηση, η οποια δεν είναι σειριακή (
ΔΕΝ αναζητά δηλαδή με τη σειρά τα στοιχεία ενός πίνακα). Λειτουργεί όμως ΜΟΝΟΝ σε ΤΑΞΙΝΟΜΗΜΕΝΟ πίνακα.
Η τεχνική της Δυαδικής Αναζήτησης βασίζεται στη στρατηγική "Διαίρει και Βασιλεύε", σύμφωνα με την οποία το γενικότερο πρόβλημα διαιρείται σε μικρότερα υπό-προβλήματα και αυτά σε ακόμη μικρότερα. Η επίλυση του γενικότερου προβλήματος έγκειται στη σταδιακή επίλυση των μικρότερων υποπροβλημάτων. Ειδικότερα, ο τρόπος που λειτουργεί η Δυαδική Αναζήτηση βασίζεται στη
μέθοδο της διχοτόμησης.
Το επόμενο πρόγραμμα δημιουργεί έναν πίνακα Ν θέσεων (με Ν<=1000) και τοποθετεί με τη σειρά τους φυσικούς αριθμούς 1,2,3,4...Ν στις αντίστοιχες θέσεις του πίνακα. Διαβάζει στη συνέχεια έναν αριθμό (
key) προς αναζήτηση. Φανταστείτε λοιπόν πως η τιμή
key δεν υπάρχει στον πίνακα. Τότε μια σειριακή αναζήτηση θα έπρεπε να εκτελέσει Ν επαναλήψεις, για να αποφανθεί πως η τιμή
key δεν υπάρχει. Η Δυαδική Αναζήτηση παρατειρείστε οτί είναι σαφώς πιο γρήγορη.
Στην περίπτωση δε, που η τιμή
key υπάρχει στον πίνακα, μια σειριακή αναζήτηση θα εκτελούσε
key επαναλήψεις, ενώ η Δυαδική Αναζήτηση παραμένει σημαντικά πιο γρήγορη.
Όλα τα προηγούμενα ισχύουν αν πίνακας έχει πάνω από περίπου 10-20 με στοιχεία, και δεν έχουν κανένα νόημα αν έχουμε ένα πίνακα με 5-10 στοιχεία.
Δοκιμάστε όμως να εκτελέσετε το επόμενο προγραμμα με Ν>400 και ίσως με έκπληξη θα διαπιστώσετε ότι η Δυαδική Αναζήτηση σπάνια εκετελεί πάνω από 7-8 ελέγχους (επαναλήψεις) (άσχετα με το αν η
key υπάρχει ή οχι στον πίνακα).
Για διδακτικούς και μονο λόγους εντάχθηκε η χρήση της μεταβλητής
ελ, η οποία επιστρέφει το πλήθος των ελέγχων που εκτέλεσε η Δυαδική Αναζήτηση.
Καλές δοκιμές.
ΠΡΟΓΡΑΜΜΑ Δυαδική_Αναζήτηση
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Ν,key,i,start,final,θεση,mid,ελ,Α[1000]
ΛΟΓΙΚΕΣ: βρέθηκε
ΑΡΧΗ
ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Δώσε πλήθος ακεραίων (1-1000)'
ΔΙΑΒΑΣΕ Ν
ΜΕΧΡΙΣ_ΟΤΟΥ (Ν>=1) ΚΑΙ (Ν<=1000)
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ Ν
Α[i] <-- i
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΡΑΨΕ 'Δώσε ακέραιο προς αναζήτηση'
ΔΙΑΒΑΣΕ key
βρέθηκε <-- ψευδής
start <-- 1
final <-- Ν
θεση <-- 0
ελ <-- 0
ΟΣΟ (start<=final) ΚΑΙ (ΟΧΙ βρέθηκε) ΕΠΑΝΑΛΑΒΕ
mid <-- (start+final) DIV 2
ΑΝ Α[mid]=key ΤΟΤΕ
θεση <-- mid
βρέθηκε <-- αληθής
ΑΛΛΙΩΣ_ΑΝ key>A[mid] ΤΟΤΕ
start <-- mid+1
ΑΛΛΙΩΣ_ΑΝ key<A[mid] ΤΟΤΕ
final <-- mid-1
ΤΕΛΟΣ_ΑΝ
ελ <-- ελ+1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ βρέθηκε ΤΟΤΕ
ΓΡΑΨΕ 'Ο αριθμός ', key,' βρέθηκε στην ', θεση,'η θέση του πίνακα'
ΑΛΛΙΩΣ
ΓΡΑΨΕ 'Ο αριθμός ',key,' δεν βρέθηκε'
ΤΕΛΟΣ_ΑΝ
ΓΡΑΨΕ 'Πραγματοποιηθηκαν ', ελ,' έλεγχοι'
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ