रेखीय खोज भनेको के हो?

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) नगण्य छ।
- तपाईलाई एकमुश्त खोज चाहिन्छ जहाँ अनुक्रमणिका बनाउनु वा पहिले क्रमबद्ध गर्नु मूल्यवान छैन।

यदि तपाई बारम्बार खोज गर्नुहुन्छ भने, क्रमबद्ध सरणीलाई बाइनरी खोज वा hash set लाई O(1) औसत खोजको लागि प्राथमिकता दिनुहोस्।

## किन यो महत्त्वपूर्ण छ

रेखीय खोज आधारभूत छ जसको विरुद्ध अन्य सबै खोजहरूको मापन गरिन्छ।

यसले तपाईलाई याद दिलाउँछ कि *सही* एल्गोरिदम डेटामा निर्भर गर्छ: अक्रमबद्ध र सानो साधारण स्क्यन पक्षमा छ; ठूलो र बारम्बार प्रश्नमा स्मार्ट संरचना पक्षमा छ।

कहिले O(n) पर्याप्त छ भनेर जान्नाले अकाल अनुकूलन रोक्छ।