Mi az lineáris keresés?

Question

Accepted Answer

**Linear search** végigolvassa a gyűjteményt elem után elemig, amíg meg nem találja a célt vagy el nem éri a végét. Bármilyen **listán** működik — rendezettől függetlenül — de **O(n)** időben fut.

## Az ötlet

Nincs feltételezés a sorrenddel kapcsolatban: csak ellenőrizze egyenként az egyes elemeket.

## Példa

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

## Bonyolultság

- **Idő:** O(n) legrosszabb eset (cél utolsó vagy hiányzik), O(1) legjobb eset.
- **Hely:** O(1).

## Mikor kell használni

- Az adatok **rendezettek** és nem engedheti meg magának a rendezést.
- A lista kicsi, így az O(n) elhanyagolható.
- Egyszeri keresésre van szüksége, ahol az index felépítése vagy az első rendezés nem érdemes.

Ha gyakran keres, akkor előnyben részesítse a rendezett tömböt bináris kereséssel vagy hash készlet az O(1) átlagos kereséseihez.

## Miért fontos

A lineáris keresés az alapvonal, amelyhez az összes többi keresés mérése történik.

Emlékeztet arra, hogy a *helyes* algoritmus az adatoktól függ: rendezetlen és apró az egyszerű vizsgálatot kedvez; nagy és többször lekérdezett az okosabb struktúrákat kedvez.

Annak tudása, hogy mikor elegendő az O(n), megelőzi az idő előtti optimalizálást.