Cad é cuardach líneach?

Question

Accepted Answer

**Linear search** scanálann bailiúchán eilimint ar eilimint go dtí go bhfaigheann sé an sprioc nó go sroicheann sé an deireadh. Oibríonn sé ar **aon** liosta — sórtáilte nó nach bhfuil — ach ritheann sé in am **O(n)**.

## An smaoineamh

Gan aon bharúlacha faoi ord: ní dhéanfaidh tú ach gach mír a sheiceáil ceann ar cheann.

## Sampla

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

## Castacht

- **Am:** O(n) sa chás is measa (sprioc deireanach nó as láthair), O(1) sa chás is fearr.
- **Spás:** O(1).

## Cathain a úsáid

- Tá na sonraí **gan sórtú** agus ní féidir leat iad a shórtú.
- Tá an liosta beag, mar sin tá O(n) neamhbhríoch.
- Tá gá agat do chuardach aonuaire inar nach bhfuil sé fiú innéacs a thógáil nó sórtáil ar dtús.

Má chuardaítear tú arís is arís eile, roghnaigh raon sórtáilte le cuardach dénártha nó tacar hash do chuardaigh O(1) ar an meán.

## An fáth ar chuir sé in iúl

Is é an cuardach líneach an bonn a dhéantar gach cuardach eile a thomhas i gcoinne.

Cuirann sé i gcuimhne duit go bhfuil an *algartam ceart* ag brath ar na sonraí: gan sórtú agus beag a bhíonn i bhfabhar an scanadh shimplí; mór agus iarratais arís is arís eile a bhíonn i bhfabhar na struchtúr níos cliste.

A bheith ar an eolas cathain a bhíonn O(n) i leor cuireann sé cosc ar bharraigheadh tobann.