Cos'è la ricerca lineare?

Question

IT Interview Practice · Accepted Answer

**Linear search** esegue una scansione di una collezione elemento per elemento finché non trova il bersaglio o raggiunge la fine. Funziona su **qualsiasi** lista — ordinata o meno — ma viene eseguita in tempo **O(n)**.

## L'idea

Nessun presupposto sull'ordine: basta controllare ogni elemento uno alla volta.

## Esempio

```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
```

## Complessità

- **Tempo:** O(n) nel caso peggiore (bersaglio ultimo o assente), O(1) nel caso migliore.
- **Spazio:** O(1).

## Quando usarla

- I dati sono **non ordinati** e non puoi permetterti di ordinarli.
- La lista è piccola, quindi O(n) è trascurabile.
- Hai bisogno di una ricerca occasionale dove costruire un indice o ordinare prima non vale la pena.

Se cerchi ripetutamente, preferisci un array ordinato con binary search o un hash set per lookups medi in O(1).

## Perché è importante

La ricerca lineare è il baseline rispetto al quale ogni altra ricerca viene misurata.

Ti ricorda che l'algoritmo *giusto* dipende dai dati: non ordinati e minuscoli favoriscono la scansione semplice; grandi e interrogati ripetutamente favoriscono strutture più intelligenti.

Sapere quando O(n) è sufficientemente buono previene l'ottimizzazione prematura.

L'idea

Esempio

Complessità

Quando usarla

Perché è importante

Domande correlate