Searching Algorithms


Linear Search

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

Η γραμμική αναζήτηση είναι ο απλούστερος αλγόριθμος αναζήτησης και ανήκει στην κατηγορία της τυφλής (brute-force) ή εξαντλητικής αναζήτησης. Η πολυπλοκότητα χειρότερης περίπτωσης είναι ανάλογη με τον αριθμό των στοιχείων της λίστας δηλαδή . Το μειονέκτημα σε σχέση με τη δυαδική αναζήτηση είναι ότι σε περίπτωση ταξινομημένης λίστας δεν το εκμεταλλεύεται, όπου και είναι καταδικασμένη να εξετάσει ολόκληρη τη λίστα.

Pseudocode

1.LinearSearch(A[0..N-1], value)
2.
for i=0:N-1

3.
if (A[i] = value)

4.
return i

5.
end if

6.
i ← i + 1

7.
end for

8.
return -1

9.end

Applet

Java applet that demonstrates linear search algorithm.

Example

Έστω ο πίνακας A=[1 2 3 4 5 6 7 8 9 10] με μήκος Ν=10. Θέλουμε να αναζητήσουμε αν ο ακέραιος 9 αποτελεί στοιχείο του Α.

Επανάληψη 1
i=0, A[0]=1, 1≠9

Το i παίρνει την τιμή 0 και το στοιχείο Α[0] ισούται με 1, το οποίο όμως διαφέρει από το ζητούμενο έτσι ο δείκτης i αυξάνεται κατά μία μονάδα.

Επανάληψη 2
i=1, A[1]=2, 2≠9

Το επόμενο στοιχείο του πίνακα είναι το 2 και είναι διαφορετικό από το 9.

…
Επανάληψη 9
i=8, A[8]=9, 9=9

Το επιθυμητό αποτέλεσμα έρχεται στην 9η επανάληψη όπου ο δείκτης i παίρνει την τιμή 8.