Kas yra tiesinė paieška?

Question

Accepted Answer

**Linear search** nuskenuoja kolekciją elementą po elemento, kol suranda tikslą arba pasiekia pabaigą. Veikia bet kuriame sąraše — surūšiuotame arba ne — bet bėga per **O(n)** laiką.

## Idėja

Jokių prielaidų apie tvarką: tiesiog patikrinkite kiekvieną elementą po vieną.

## Pavyzdys

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

## Sudėtingumas

- **Laikas:** O(n) blogiausias atvejis (tikslas paskutinis arba neegzistuoja), O(1) geriausias atvejis.
- **Vieta:** O(1).

## Kada naudoti

- Duomenys yra **nesutvarkyta** ir negalite jų surūšiuoti.
- Sąrašas mažas, todėl O(n) yra nepastebimas.
- Jums reikalinga vienkartinė paieška, kur indekso kūrimas arba rūšiavimas iš anksto nevertas.

Jei paieškote pakartotinai, pirmenybę teikite surūšiuotam masyvui su binary search arba hash set dėl O(1) vidutinio paieško.

## Kodėl tai svarbu

Tiesinė paieška yra pagrindinis standartas, prieš kurį matuojamos visos kitos paieškos.

Tai primena jums, kad *tinkamas* algoritmas priklauso nuo duomenų: nesutvarkyta ir maža palaiko paprastą skenavimą; didelė ir pakartotinai klausiama palaiko gudresnių struktūrų.

Žinant, kada O(n) yra pakankamai gera, išvengiama prematurios optimizacijos.