1. Σειριακή Αναζήτηση (Γραμμική)
Ορισμός
Η σειριακή αναζήτηση είναι η πιο απλή μέθοδος. Εξετάζουμε τα στοιχεία του πίνακα ένα προς ένα από την αρχή μέχρι το τέλος, μέχρι να βρούμε το ζητούμενο ή να εξαντλήσουμε τα στοιχεία.
Βασικά χαρακτηριστικά
- Δεν απαιτεί ταξινόμηση του πίνακα.
- Λειτουργεί σε οποιονδήποτε πίνακα (ταξινομημένο ή μη).
- Εύκολη στην υλοποίηση.
- Μπορεί να τερματίσει νωρίτερα αν βρεθεί το στοιχείο (π.χ. με την εντολή ΔΙΑΚΟΠΗ στη ΓΛΩΣΣΑ).
- Χρήσιμη σε μικρούς πίνακες ή όταν η αναζήτηση γίνεται σπάνια.
Περιορισμοί
- Σε μεγάλους πίνακες είναι αργή, γιατί μπορεί να χρειαστεί να εξετάσουμε όλα τα στοιχεία.
- Πολύ χαμηλή αποδοτικότητα για συχνές αναζητήσεις σε μεγάλα σύνολα δεδομένων.
Παράδειγμα ψευδοκώδικα (ΓΛΩΣΣΑ):
Βρέθηκε ← ΨΕΥΔΗΣ
Για i από 1 μέχρι Ν
Αν Α[i] = x τότε
Βρέθηκε ← ΑΛΗΘΗΣ
Θέση ← i
ΔΙΑΚΟΠΗ
Τέλος_αν
Τέλος_επανάληψης
Αν Βρέθηκε τότε
Γράψε 'Το στοιχείο βρέθηκε στη θέση', Θέση
Αλλιώς
Γράψε 'Το στοιχείο δεν βρέθηκε'
Τέλος_αν
2. Δυαδική Αναζήτηση
Ορισμός
Η δυαδική αναζήτηση είναι πολύ πιο αποδοτική, αλλά εφαρμόζεται μόνο σε ταξινομημένους πίνακες. Η μέθοδος βασίζεται στην αρχή "διαίρει και βασίλευε":
Σε κάθε βήμα συγκρίνουμε το ζητούμενο στοιχείο με το μεσαίο του πίνακα:
- Αν είναι ίσο, βρήκαμε το στοιχείο.
- Αν είναι μικρότερο, συνεχίζουμε στο αριστερό μισό.
- Αν είναι μεγαλύτερο, συνεχίζουμε στο δεξί μισό.
Βασικά χαρακτηριστικά
- Απαιτεί ταξινομημένο πίνακα.
- Σε κάθε βήμα αποκλείεται το μισό των στοιχείων.
- Πολύ γρήγορη για μεγάλους πίνακες (χρόνος εκτέλεσης O(log n)).
Περιορισμοί
- Δεν μπορεί να εφαρμοστεί σε μη ταξινομημένους πίνακες.
- Η προετοιμασία (ταξινόμηση) μπορεί να είναι χρονοβόρα αν δεν είναι ήδη ταξινομημένος.
Παράδειγμα ψευδοκώδικα (ΓΛΩΣΣΑ):
Αρχή ← 1
Τέλος ← Ν
Βρέθηκε ← ΨΕΥΔΗΣ
Όσο Αρχή <= Τέλος και Βρέθηκε = ΨΕΥΔΗΣ επανάλαβε
Μέσος ← (Αρχή + Τέλος) DIV 2
Αν Α[Μέσος] = x τότε
Βρέθηκε ← ΑΛΗΘΗΣ
Θέση ← Μέσος
Αλλιώς_αν Α[Μέσος] < x τότε
Αρχή ← Μέσος + 1
Αλλιώς
Τέλος ← Μέσος - 1
Τέλος_αν
Τέλος_επανάληψης
Αν Βρέθηκε τότε
Γράψε 'Το στοιχείο βρέθηκε στη θέση', Θέση
Αλλιώς
Γράψε 'Το στοιχείο δεν βρέθηκε'
Τέλος_αν