ਰੇਖੀ ਖੋਜ ਕੀ ਹੈ?

Question

ਰੇਖੀ ਖੋਜ ਕੀ ਹੈ?

Accepted Answer

**ਰੇਖੀ ਖੋਜ** ਇੱਕ ਸੰਗ੍ਰਹਿ ਨੂੰ ਤੱਤ ਦੇ ਤੱਤ ਸਕੈਨ ਕਰਦੀ ਹੈ ਜਦੋਂ ਤੱਕ ਇਹ ਟੀਚਾ ਨਹੀਂ ਲੱਭ ਲੈਂਦੀ ਜਾਂ ਅੰਤ ਤੱਕ ਪਹੁੰਚ ਜਾਂਦੀ ਹੈ। ਇਹ **ਕਿਸੇ ਵੀ** ਸੂਚੀ 'ਤੇ ਕੰਮ ਕਰਦੀ ਹੈ — ਛਾਂਟੀ ਹੋਈ ਜਾਂ ਨਹੀਂ — ਪਰ **O(n)** ਸਮੇਂ ਵਿੱਚ ਚਲਦੀ ਹੈ।

## ਵਿਚਾਰ

ਕ੍ਰਮ ਬਾਰੇ ਕੋਈ ਮਾਨਤਾਵਾਂ ਨਹੀਂ: ਸਿਰਫ ਹਰੇਕ ਆਈਟਮ ਨੂੰ ਇੱਕ ਵਾਰ ਚੇਕ ਕਰੋ।

## ਉਦਾਹਰਨ

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

## ਗੁੰਝਲਦਾਰਤਾ

- **ਸਮਾਂ:** O(n) ਸਭ ਤੋਂ ਮਾੜਾ ਕੇਸ (ਟੀਚਾ ਆਖਰੀ ਜਾਂ ਮੌਜੂਦ ਨਹੀਂ), O(1) ਸਭ ਤੋਂ ਵਧੀਆ ਕੇਸ।
- **ਥਾਂ:** O(1)।

## ਕਦੋਂ ਵਰਤਿਆ ਜਾਵੇ

- ਡੇਟਾ **ਛਾਂਟਿਆ ਗਿਆ ਨਹੀਂ** ਹੈ ਅਤੇ ਤੁਸੀਂ ਇਸਨੂੰ ਛਾਂਟ ਨਹੀਂ ਸਕਦੇ।
- ਸੂਚੀ ਛੋਟੀ ਹੈ, ਇਸਲਈ O(n) ਮਾਮੂਲੀ ਹੈ।
- ਤੁਹਾਨੂੰ ਇੱਕ ਵਾਰੀ ਖੋਜ ਦੀ ਲੋੜ ਹੈ ਜਿੱਥੇ ਪਹਿਲਾ ਇੰਡੈਕਸ ਬਣਾਉਣਾ ਜਾਂ ਛਾਂਟਣਾ ਕੀਮਤੀ ਨਹੀਂ ਹੈ।

ਜੇਕਰ ਤੁਸੀਂ ਵਾਰ-ਵਾਰ ਖੋਜ ਕਰਦੇ ਹੋ, ਤਾਂ O(1) ਔਸਤ ਖੋਜ ਲਈ ਛਾਂਟੀ ਹੋਈ ਐਰੇ ਨਾਲ binary search ਜਾਂ hash set ਨੂੰ ਤਰਜੀਹ ਦਿਓ।

## ਇਹ ਮਹੱਤਵਪੂਰਨ ਕਿਉਂ ਹੈ

ਰੇਖੀ ਖੋਜ ਉਹ ਆਧਾਰ ਹੈ ਜਿਸਦੇ ਵਿਰੁੱਧ ਸਭ ਜ਼ਿਆਦਾ ਖੋਜਾਂ ਨੂੰ ਮਾਪਿਆ ਜਾਂਦਾ ਹੈ।

ਇਹ ਤੁਹਾਨੂੰ ਯਾਦ ਦਿਵਾਉਂਦਾ ਹੈ ਕਿ *ਸਹੀ* ਅਲਗੋਰਿਦਮ ਡੇਟਾ 'ਤੇ ਨਿਰਭਰ ਕਰਦਾ ਹੈ: ਛਾਂਟਿਆ ਗਿਆ ਨਹੀਂ ਅਤੇ ਛੋਟਾ ਸਧਾਰਨ ਸਕੈਨ ਨੂੰ ਤਰਜੀਹ ਦਿੰਦਾ ਹੈ; ਵੱਡਾ ਅਤੇ ਵਾਰ-ਵਾਰ ਪੁੱਛਿਆ ਗਿਆ ਸਮਾਰਟ ਢਾਂਚੇ ਨੂੰ ਤਰਜੀਹ ਦਿੰਦਾ ਹੈ।

ਜਾਣਨਾ ਕਿ ਕਦੋਂ O(n) ਕਾਫੀ ਚੰਗਾ ਹੈ ਜਲਦਬਾਜ਼ੀ ਵਿੱਚ ਅਨੁਕੂਲਨ ਨੂੰ ਰੋਕਦਾ ਹੈ।