Çfarë është kërkimi linear?

Question

Accepted Answer

**Kërkimi linear** skanon një koleksion element pas elementi derisa të gjejë objektivin ose të arrijë në fund. Funksionon në **çdo** listë — të sortuar ose jo — por bëhet në kohë **O(n)**.

## Ideja

Asnjë supozim për rendin: thjesht kontrollo secilin element një e nga një.

## Shembull

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

## Kompleksiteti

- **Kohë:** O(n) rasti më i keq (objektivi i fundit ose mungon), O(1) rasti më i mirë.
- **Hapësirë:** O(1).

## Kur të përdorni

- Të dhënat janë **të parenditura** dhe nuk mund t'i sortoni.
- Lista është e vogël, kështu që O(n) është i papërfillshëm.
- Ju keni nevojë për një kërkesë të vetme ku ndërtimi i një indeksi ose sortimi nuk ia vlen.

Nëse kërkoni shumë herë, preferohet një grup i sortuar me kërkimin binar ose një set hash për kërkime mesatare O(1).

## Pse është e rëndësishme

Kërkimi linear është bazaleja ndaj të cilës matet çdo kërkimi tjetër.

Ju kujton se *algoritmi i duhur* varet nga të dhënat: të padrendura dhe të vogla favorizojnë skanimin e thjeshtë; të mëdha dhe të kërkuara me shumë shprehje favorizojnë struktura më të zgjuara.

Dija kur O(n) është mjaft mirë parandalon optimizimin e parakohshëm.