లీనియర్ సర్చ్ అంటే ఏమిటి?

Question

Accepted Answer

**లీనియర్ సర్చ్** ఒక సంગ్రహణను మూలకం by మూలకం స్కాన్ చేస్తుంది, లక్ష్యను కనుగొనే వరకు లేదా చివరకు చేరుకునే వరకు. ఇది **ఏదైనా** జాబితాలో పని చేస్తుంది — సంబంధితమైనవి లేదా కాని — కానీ **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) సరాసరి సర్చ్ కోసం హ్యాష్ సెట్ ఉపయోగించండి.

## ఎందుకు ఇది ముఖ్యమైనది

లీనియర్ సర్చ్ ఇతర అన్ని సర్చ్ కట్టుబాటుగా వర్తించే ప్రాథమిక.

*సరైన* అల్గారిథమ్ డేటాపై ఆధారపడి ఉంటుందని ఇది మీకు గుర్తు చేస్తుంది: సంబంధితం కాని మరియు చిన్నవి సాధారణ స్కానను ఐచ్ఛికం చేస్తాయి; పెద్దవి మరియు పదేపదే జిజ్ఞాసించినవి తెలివైన నిర్మాణాలను ఐచ్ఛికం చేస్తాయి.

O(n) ఎప్పుడు సరిపోతుందో తెలుసుకోవడం ముందస్తు ఆప్టిమైజేషన్‌ను నిరోధిస్తుంది.