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

Question

IT Interview Practice · 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) पर्याप्त है, समयपूर्व अनुकूलन को रोकता है।

विचार

उदाहरण

जटिलता

कब उपयोग करें

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

संबंधित प्रश्न