Τι είναι η γραμμική αναζήτηση;

Question

Accepted Answer

**Η γραμμική αναζήτηση** σαρώνει μια συλλογή στοιχείο προς στοιχείο μέχρι να βρει το στόχο ή να φτάσει στο τέλος. Λειτουργεί σε **οποιαδήποτε** λίστα — ταξινομημένη ή όχι — αλλά εκτελείται σε **O(n)** χρόνο.

## Η ιδέα

Κανένες υποθέσεις σχετικά με την σειρά: απλώς ελέγχουμε κάθε στοιχείο ένα προς ένα.

## Παράδειγμα

```python
def linear_search(arr, target):
    for i, value in enumerate(arr):   # walk left to right
        if value == target:
            return i                  # return the index when found
    return -1                         # not found after full scan

linear_search([4, 2, 7, 1], 7)        # -> 2
```

## Πολυπλοκότητα

- **Χρόνος:** O(n) χειρότερη περίπτωση (στόχος τελευταίος ή απών), O(1) καλύτερη περίπτωση.
- **Χώρος:** O(1).

## Πότε να χρησιμοποιήσετε

- Τα δεδομένα είναι **ταξινόμητα** και δεν μπορείτε να τα ταξινομήσετε.
- Η λίστα είναι μικρή, οπότε O(n) είναι αμελητέο.
- Χρειάζεστε μια μοναδική αναζήτηση όπου η δημιουργία ενός ευρετηρίου ή η ταξινόμηση πρώτα δεν αξίζει τον κόπο.

Αν αναζητάτε επανειλημμένα, προτιμήστε έναν ταξινομημένο πίνακα με binary search ή ένα hash set για O(1) μέσες αναζητήσεις.

## Γιατί έχει σημασία

Η γραμμική αναζήτηση είναι η βάση κατά την οποία μετράται κάθε άλλη αναζήτηση.

Σας υπενθυμίζει ότι ο *σωστός* αλγόριθμος εξαρτάται από τα δεδομένα: ταξινόμητα και μικρά προτιμούν την απλή σάρωση· μεγάλα και επανειλημμένα ερωτήματα προτιμούν πιο έξυπνες δομές.

Το να γνωρίζετε πότε O(n) είναι αρκετό αποτρέπει την πρόωρη βελτιστοποίηση.