Αναζήτηση

Εισαγωγή

Οι αλγόριθμοι αναζήτησης (searching algorithms) επιτρέπουν την εύρεση ενός στοιχείου σε μια δομή δεδομένων με βάση ένα χαρακτηριστικό του.
Αν τα στοιχεία είναι οργανωμένα σε εγγραφές (records) και κάθε μια από αυτές απαρτίζεται από πεδία (fields) τότε το πεδίο με βάση το οποίο γίνεται η αναζήτηση ονομάζεται κλειδί (key) της αναζήτησης.
Το κόστος μιας αναζήτησης εκφράζεται ανάλογα με τον αριθμό συγκρίσεων που απαιτούνται κατά μέσο όρο για την εύρεση της αναζητούμενης εγγραφής.

Στη σειριακή αναζήτηση (sequential search) η εύρεση της εγγραφής στον πίνακα γίνεται ελέγχοντας μια-μια τις εγγραφές από την αρχή μέχρι το τέλος του πίνακα.
Αν ο πίνακας έχει Ν στοιχεία θα απαιτηθούν κατά μέσο όρο N / 2 συγκρίσεις.

Στην αναζήτηση κατά ομάδες (group search) η εύρεση της εγγραφής στον πίνακα γίνεται χωρίζοντας τον (ταξινομημένο) πίνακα σε Μ ομάδες και ελέγχοντας πρώτα σε ποια ομάδα ανήκει η εγγραφή και στη συνέχει ελέγχοντας μια-μια τις εγγραφές από την αρχή μέχρι το τέλος της συγκεκριμένης ομάδας.
Ο βέλτιστος αριθμός ομάδων είναι sqrt(N).
Αν ο πίνακας έχει Ν στοιχεία και Μ ομάδες θα απαιτηθούν κατά μέσο όρο Ν/(2Μ) + Μ / 2 συγκρίσεις.

Στη δυαδική αναζήτηση (binary search) η εύρεση της εγγραφής στον (ταξινομημένο) πίνακα γίνεται αναζητώντας το στοιχείο στη μέση του πίνακα, στη συνέχεια στη μέση της μέσης κ.ο.κ.
Αν ο πίνακας έχει Ν στοιχεία θα απαιτηθούν κατά μέσο όρο log2 N συγκρίσεις.

Στη αναζήτηση παρεμβολής (interpolation search) η εύρεση της εγγραφής στον (ταξινομημένο) πίνακα γίνεται υπολογίζοντας την πιθανή θέση της εγγραφής σε σχέση με τις τιμές των στοιχείων στα άκρα της περιοχής αναζήτησης. Ανάλογα με τη σύγκριση της τιμής της εγραφής με την εγγραφή στην πιθανή θέση αναπροσαρμόζεται το αντίστοιχο άκρο.
Αν ο πίνακας έχει στοιχεία ομοιόμορφα κατανεμημένα θα απαιτηθούν O(log log n) συγκρίσεις.

Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 107-118 Εκδόσεις Νέων Τεχνολογιών, 1993.
Donald E. Knuth. The Art of Computer Programming, volume 3 / Searching and Sorting. Addison-Wesley, second edition, 1973.
Niklaus Wirth. Algorithms + Datastructures = Programs. p. 56-72. Prentice-Hall, 1976.