Τι είναι η αναζήτηση

Όταν θέλουμε να αναζητήσουμε ένα στοιχείο σε ένα πίνακα έχουμε στη διάθεσή μας διάφορους τρόπους να το κάνουμε. Δυο από αυτούς είναι η σειριακή και η δυαδική αναζήτηση.

Η σειριακή αναζήτηση είναι πιο εύκολος τρόπος αναζήτησης αλλά και λιγότερο αποδοτικός σε σύγκριση με τη δυαδική .
 Ισχύει όμως πάντα αυτό;

Για να απαντήσουμε τεκμηριωμένα σε αυτό το ερώτημα πρέπει να μελετήσουμε λίγο τον τρόπο λειτουργίας τους και να συγκρίνουμε ποιοτικά τις αποδόσεις τους σε διάφορα σενάρια λειτουργίας.
Η χρήση της σειριακής αναζήτησης , σύμφωνα με την παράγραφο 3.6 του σχολικού βιβλίου , δικαιολογείται μόνο σε περιπτώσεις όπου:

• ο πίνακας είναι μη ταξινομημένος,
• ο πίνακας είναι μικρού μεγέθους (για παράδειγμα, n ≤ 20),
• η αναζήτηση σε ένα συγκεκριμένο πίνακα γίνεται σπάνια,

Από την άλλη πλευρά, η δυαδική αναζήτηση είναι πολύ πιο αποδοτική , με την βασική προϋπόθεση ότι ο πίνακας είναι ταξινομημένος.

Σειριακή Αναζήτηση

Ο αλγόριθμος της σειριακής αναζήτησης είναι ο ακόλουθος :
Όπου n=το πλήθος των θέσεων του πίνακα,
                Table = ο πίνακας στον οποίο γίνεται η αναζήτηση και
                Key = το υπο αναζήτηση στοιχείο
 
Αλγόριθμος Sequential_Search
Δεδομένα // n, table, key //
done ← ψευδής
position ← 0
i ← 1
Όσο (done=ψευδής) και (i<=n) επανάλαβε
          Αν table[i]=key τότε
               done ← αληθής
               position ← i
          αλλιώς
               i ← i+1
          Τέλος_αν
Τέλος_επανάληψης
Αποτελέσματα //done, position //
Τέλος Sequential_Search
 
Παρατηρούμε ότι η λειτουργία της σειριακής αναζήτησης ξεκινά από την πρώτη θέση του πίνακα και ελέγχει μια-μια κάθε θέση για να διαπιστώσει την ύπαρξη ή όχι του υπο αναζήτηση στοιχείου. Όταν το βρει τότε σταματά τις επαναλήψεις και εμφανίζει τη θέση του στοιχείου στον πίνακα.
Αν το στοιχείο βρίσκεται στις πρώτες θέσεις του πίνακα, τότε η αναζήτηση θα ολοκληρωθεί πολύ γρήγορα και θα έχει πολύ καλή απόδοση. Όσο πιο ¨μακριά¨ από την αρχή του πίνακα βρίσκεται το στοιχείο τόσο λιγότερο αποδοτική θα είναι και η αναζήτηση.

Δυαδική Αναζήτηση

Η δυαδική αναζήτηση στηρίζει τη λειτουργία της στο γεγονός ότι ο πίνακας είναι ταξινομημένος. Έτσι με χρήση δυο δεικτών του L ( Left ) και του R ( Right ) καθορίζει αρχικά την αρχή και το τέλος του πίνακα. Από τις τιμές των δυο αυτών δεικτών υπολογίζει τη μεσαία θέση του πίνακα (Mß(L+R) DIV 2) και εκεί κάνει τη σύγκριση με το στοιχείο που ψάχνει. Αν το στοιχείο που υπάρχει στη μεσαία θέση είναι μικρότερο από αυτό που ψάχνουμε τότε το τελευταίο αποκλείεται να βρίσκεται αριστερά από τη θέση του Μ , άρα μετακινεί τον δείκτη L μια θέση δεξιά από το M ορίζοντας έτσι μια άλλη περιοχή του πίνακα στην οποία θα γίνει η αναζήτηση . Στην πραγματικότητα αφαιρεί από την αναζήτηση το τμήμα του πίνακα που βρίσκεται αριστερά του Μ . Το αντίστοιχο συμβαίνει αν το στοιχείο που περιέχεται στη θέση Μ είναι μεγαλύτερο από αυτό που ψάχνουμε.
Όλη αυτή η διαδικασία έχει ως αποτέλεσμα την ταχύτατη εύρεση του υπο αναζήτηση στοιχείου.


Αλγόριθμος δυαδική_αναζήτηση
Δεδομένα // n, table, key //
L←1
R←n
D←ΨΕΥΔΗΣ
Όσο D=ΨΕΥΔΗΣ και L<=R επανάλαβε
                M←(L+R) DIV 2
                Αν table[M] = key τότε
                                D← ΑΛΗΘΗΣ
                Αλλιώς_αν table[M]<key τότε 
                                L←M+1
                Αλλιώς
                                R←M-1
                Τέλος_αν
Τέλος_επανάληψης
Αν D = ΑΛΗΘΗΣ τότε
                Εμφάνισε ‘Βρέθηκε το στοιχείο στη θέση:’,Μ
Αλλιώς
                Εμφάνισε ‘Δεν βρέθηκε το στοιχείο’
Τέλος_αν
Τέλος δυαδική_αναζήτηση

Γενικά

Τι γίνεται αν δεν υπάρχει το υπο αναζήτηση στοιχείο στον πίνακα;
Ακόμη και στην περίπτωση που το υπο αναζήτηση στοιχείο δεν υπάρχει στον πίνακα, η σάρωση του πίνακα γίνεται πολύ γρήγορα. Για παράδειγμα σε ένα πίνακα με 200 θέσεις αν δεν υπάρχει το υπο αναζήτηση στοιχείο η σειριακή αναζήτηση θα πραγματοποιήσει 200 επαναλήψεις για να καταλήξει στο αποτέλεσμα, αντίστοιχα η δυαδική δεν θα χρειαστεί περισσότερες από 7 με 8 επαναλήψεις!
Τι γίνεται αν το υπο αναζήτηση στοιχείο είναι σε μια από τις πρώτες θέσεις του πίνακα;
Όλοι οι κανόνες έχουν και εξαιρέσεις! Εδώ λοιπόν, αν το υπο αναζήτηση στοιχείο βρίσκεται σε μια από τις πρώτες θέσεις του πίνακα , τότε η σειριακή αναζήτηση είναι γρηγορότερη από τη δυαδική ! Είναι η μόνη περίπτωση στην οποία ¨κερδίζει¨ τη μάχη της αναζήτησης η σειριακή ! Σε όλες τις υπόλοιπες η δυαδική είναι σαφώς πιο γρήγορη, εφ όσων μιλάμε για ταξινομημένο πίνακα, μη το ξεχνάμε!