રેખીય શોધ શું છે?

Question

રેખીય શોધ શું છે?

Accepted Answer

**Linear search** કલેક્શનને એક એક ઘટક દ્વારા સ્કેન કરે છે જ્યાં સુધી તે લક્ષ્ય શોધે નહીં અથવા અંતે પહોંચે નહીં. તે **કોઈપણ** સૂચીમાં કાર્ય કરે છે — સાજેલી હોય કે ન હોય — પરંતુ **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) સરેરાશ લુકઅપ્સ માટે દ્વિસંગી શોધ અથવા hash set સાથે સાજેલ અરે પસંદ કરો.

## તે શા માટે મહત્વપૂર્ણ છે

રેખીય શોધ બેસલાઈન છે જેની સામે બીજી તમામ શોધો માપવામાં આવે છે.

તે તમને યાદ કરાવે છે કે *સાચો* અલ્ગોરિધમ ડેટા પર આધાર રાખે છે: અસાજેલો અને નાનો સરળ સ્કેનને અનુકૂળ કરે છે; મોટો અને વારંવાર પૂછવામાં આવતો સ્મার્ટર સ્ટ્રક્ચર્સને અનુકૂળ કરે છે.

જાણવું કે કયારે O(n) પર્યાપ્ત છે અકાલીન ઑપ્ટિમાઇઝેશનને અટકાવે છે.