रेखीय शोध म्हणजे काय?

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) नगण्य है।
- आपको एक बार का लुकअप चाहिए जहां अनुक्रमणिका बनाना या पहले सॉर्ट करना सार्थक नहीं है।

यदि आप बार-बार खोज करते हैं, तो binary search के साथ सॉर्ट किए गए array या O(1) औसत लुकअप के लिए hash set को प्राथमिकता दें।

## यह महत्वपूर्ण क्यों है

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

यह आपको याद दिलाता है कि *सही* एल्गोरिदम डेटा पर निर्भर करते हैं: अक्रमबद्ध और छोटा सरल स्कैन का समर्थन करता है; बड़ा और बार-बार क्वेरी किया गया चतुर संरचनाओं का समर्थन करता है।

यह जानना कि कब O(n) पर्याप्त है, समयपूर्व अनुकूलन को रोकता है।