ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ

Показать описание

ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ(Binary search algorithm)
Να περιγραφεί η ΔΥΑΔΙΚΗ ΑΝΑΖΗΤΗΣΗ ακεραίου Χ σε ένα ΤΑΞΙΝΟΜΗΜΕΝΟ ΠΙΝΑΚΑ ακεραίων 100 αριθμών.
Η δυαδική αναζήτηση εφαρμόζεται μόνο σε ταξινομημένους πίνακες.
Για παράδειγμα έστω ο παρακάτω ταξινομημένος πίνακας:
Έστω ότι αναζητούμε αν υπάρχει το στοιχείο 17 στον πίνακα
και επιστρέφουμε ως απάντηση τη θέση του πίνακα που βρίσκεται το στοιχείο με τιμή 5.
Η κεντρική ιδέα είναι :
Εξετάζω το κεντρικό στοιχείο του πίνακα:
Αν το στοιχείο που αναζητάμε είναι το κεντρικό στοιχείο
τότε ολοκληρώσαμε την δυαδική αναζήτηση.
Στη περίπτωση μας δεν συμβαίνει αυτό.
Στη συνέχεια εξετάζουμε αν το στοιχείο που αναζητούμε είναι μικρότερο ή μεγαλύτερο
από το κεντρικό στοιχείο.
Στην περίπτωση μας είναι μικρότερο από το κεντρικό στοιχείο ,
οπότε ψάχνουμε αριστερά από το κεντρικό στοιχείο.
δεν ασχολούμαστε με τα στοιχεία στα δεξιά .
Αν το Χ είναι το στοιχείο στη νέα κεντρική θέση 4 του νέου πίνακα που δημιουργήθηκε .
Τότε επιστρέφουμε τη θέση του στοιχείου
Αυτό δεν ισχύει
και εξετάζουμε ξανά, αν το στοιχείο που ψάχνουμε
είναι μεγαλύτερο ή μικρότερο του νέου κεντρικού στοιχείου.
Και δεν ασχολούμαστε με τα στοιχεία αριστερά του νέου κεντρικού στοιχείου.
Εξετάζουμε πάλι αν το στοιχείο που αναζητούμε είναι το νέο κεντρικό στοιχείο.
Δεν είναι ξανά, οπότε συγκρίνουμε με το νέο κεντρικό στοιχείο
αν είναι μεγαλύτερο ή μικρότερο.
Απορρίπτουμε τα στοιχεία δεξιά του νέου κεντρικού στοιχείου.
Και καταλήξαμε να βρούμε το στοιχείο που αναζητούμε στη θέση 5.
ΑΥΞΟΥΣΑ ΤΑΞΙΝΟΜΗΣΗ
Αλγόριθμος ΔυαδικήΑναζήτηση
Για i από 1 μέχρι 100
Εμφάνισε “Δώσε το στοιχείο”,i, “του πίνακα Α”
Διάβασε Α[ i ]
Τέλος_επανάληψης
Εμφάνισε “Δώσε τον αριθμό αναζήτησης στον πίνακα Α”
Διάβασε στοιχείο
αρχή← 1
τέλος← 100
μέση← (αρχή + τέλος)div2
Όσο αρχή μικροτερο ή ίσο τελος ΚΑΙ Α[μέση]διαφορο στοιχείο επανάλαβε
Αν στοιχείο μικροτερο Α[μέση] τότε
τέλος← μέση-1
Αλλιώς
αρχή← μέση+1
Τέλος_αν
μέση←(αρχή + τέλος)div2
Τέλος_επανάληψης
Αν Α[μέση] = στοιχείο τότε
Εμφάνισε “Βρέθηκε στη θέση”,μέση
Αλλιώς
Εμφάνισε “Δεν βρέθηκε”
Τέλος_αν

Τέλος ΔυαδικήΑναζήτηση

ΦΘΙΝΟΥΣΑ ΤΑΞΙΝΟΜΗΣΗ
Αλγόριθμος ΔυαδικήΑναζήτηση
Για i από 1 μέχρι 100
Εμφάνισε “Δώσε το στοιχείο”,i, “του πίνακα Α”
Διάβασε Α[ i ]
Τέλος_επανάληψης
Εμφάνισε “Δώσε τον αριθμό αναζήτησης στον πίνακα Α”
Διάβασε στοιχείο
αρχή← 1
τέλος← 100
μέση← (αρχή + τέλος)div2
Όσο αρχή μικροτερο ή ίσο τελος ΚΑΙ Α[μέση]διαφορο στοιχείο επανάλαβε
Αν στοιχείο μικροτερο Α[μέση] τότε
αρχή← μέση+1
Αλλιώς
τέλος← μέση-1
Τέλος_αν
μέση←(αρχή + τέλος)div2
Τέλος_επανάληψης
Αν Α[μέση] = στοιχείο τότε
Εμφάνισε “Βρέθηκε στη θέση”,μέση
Αλλιώς
Εμφάνισε “Δεν βρέθηκε”
Τέλος_αν
Τέλος ΔυαδικήΑναζήτηση
ΠΡΟΕΤΟΙΜΑΣΙΑ ΠΑΝΕΛΛΗΝΙΩΝ
SPYROS ZYGOURIS
Σπύρος Ζυγούρης
Ανάπτυξη Εφαρμογων σε Προγραμματιστικο Περιβαλλον.
pseudocode