X'inhu linear search?

Question

Accepted Answer

**Linear search** jiskan kolezzjoni element per element sal-ma jsib it-target jew jintlaqa' mat-tmiem. Jaħdem fuq **kwalunkwe** lista — magħżula jew le — iżda jaħdem fil-ħin **O(n)**.

## L-idea

L-ebda assunzjoni dwar l-ordni: sempliċement iċċekja kull item waħda waħda.

## Eżempju

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

## Kumplessità

- **Ħin:** O(n) agħar każ (target l-aħħar jew neqes), O(1) aħjar każ.
- **Spazju:** O(1).

## Meta tużaha

- Id-data hija **mhux magħżula** u int ma tistax tmagħżuha.
- Il-lista żgħira, għalhekk O(n) hija negliġibbli.
- Int għandek bżonn tiftix waħda biss fejn l-ħolqien ta' indiċi jew l-magħżul l-ewwel mhuwiex il-ħadd.

Ikkunsidra binary search ma' array magħżul jew hash set għal dawk li jfittxu aktar minn darba għal O(1) medja.

## Għalfejn importanti

Linear search hija l-linji baża li kontra liema l-otri ftit jitkejjlu.

Għandek tiftakar li l-algoritmu *dritt* jiddependi fuq id-data: mhux magħżula u żgħira favur l-iskennjar sempliċi; kbira u mitkejjla mririja favur strutturi aktar intelliġenti.

Il-għarfien meta O(n) huwa biżżejjed jipprevjeni l-ottimizzazzjoni prematura.