Python में Linear Search: शुरुआती मार्गदर्शिका व उदाहरण

सर्च एल्गोरिदम की बात हो तो लीनियर सर्च सबसे सरल तरीकों में से एक है। यदि आपने कभी किसी सूची में आइटम्स को एक-एक करके तब तक देखा है जब तक मनचाही चीज़ नहीं मिल गई, तो आपने पहले ही लीनियर सर्च कर लिया है!

समझने में आसान होने के अलावा, लीनियर सर्च उपयोगी है क्योंकि यह अन्य कुछ सर्च एल्गोरिदम्स के विपरीत, असॉर्टेड डेटा पर भी काम करता है। यह बहुमुखीपन उन स्थितियों में इसे उपयोगी विकल्प बनाता है जहाँ डेटा को सॉर्ट करना संभव नहीं है। मैं इस ट्यूटोरियल में Python का उपयोग करूँगा, तो यदि शुरू करने से पहले आप Python का रिफ्रेशर चाहते हैं, तो Python Programming स्किल ट्रैक देखें।

Linear Search क्या है?

लीनियर सर्च एक एल्गोरिदम है जो सूची में किसी विशेष वैल्यू को हर एलिमेंट को एक-एक करके जाँचकर खोजता है। यह पहले आइटम से शुरू करता है, उसे लक्ष्य से तुलना करता है, और तब तक आगे बढ़ता है जब तक लक्ष्य न मिल जाए या सूची का अंत न आ जाए। यह एक सरल और सहज एल्गोरिदम है।

लीनियर सर्च काम करने के लिए डेटा के सॉर्टेड होने की आवश्यकता नहीं होती, इसलिए यह मुख्यतः असॉर्टेड डाटासेट्स में उपयोग होता है। यह उन स्थितियों में सुविधाजनक है जहाँ सॉर्टिंग व्यावहारिक नहीं है, या आप कच्चे डेटा पर काम कर रहे हैं। हालाँकि, यह लाभ एक कीमत पर आता है: यह उन अन्य एल्गोरिदम्स जितना कुशल नहीं है जिन्हें प्रीसॉर्टेड डेटा चाहिए।

लीनियर सर्च उन स्थितियों में आदर्श है जहाँ आप तुलनात्मक रूप से छोटे डाटासेट्स पर काम कर रहे हों या डेटा को सॉर्ट करना संभव न हो। नीचे का आरेख एक सरलीकृत व्याख्या देता है।

Linear Search का चयन

आइए फायदों पर नज़र डालें और साथ ही एक प्रमुख कमी पर भी: 

Linear Search क्यों चुनें?

मेरे विचार में, लीनियर सर्च के तीन स्पष्ट लाभ हैं:

जब सादगी सबसे महत्वपूर्ण हो

लीनियर सर्च का सबसे बड़ा फायदा इसकी सादगी है। एल्गोरिदम समझने और लागू करने में आसान है। जटिल सॉर्टिंग या डेटा को बाँटने की चिंता नहीं करनी होती। बस सूची की शुरुआत से शुरू करें और तब तक हर एलिमेंट देखें जब तक आपको मनचाही चीज़ न मिल जाए।

जब आपके पास सॉर्ट करने का समय न हो

बाइनरी सर्च जैसे अन्य सर्च एल्गोरिदम्स के विपरीत, लीनियर सर्च में डाटासेट का सॉर्टेड होना जरूरी नहीं है। इसलिए जब आपको जल्दी में कुछ ढूंढना हो तो यह बिल्कुल उपयुक्त है।

जब आपको बहुमुखीपन चाहिए

लीनियर सर्च का एक और फायदा यह है कि यह बहुमुखी है। यह केवल arrays के साथ ही नहीं, अन्य Python डेटा स्ट्रक्चर्स जैसे linked lists के साथ भी काम करता है। जब तक आप एलिमेंट्स तक क्रमिक रूप से पहुँच सकते हैं, लीनियर सर्च काम कर सकता है। यह संख्याओं, स्ट्रिंग्स, यहाँ तक कि ऑब्जेक्ट्स जैसे अलग-अलग डेटा टाइप्स को संभालने के लिए पर्याप्त लचीला है।

Linear Search पर दो बार क्यों सोचें?

एक मुद्दा ध्यान देने योग्य है:

जब दक्षता मायने रखती है

लीनियर सर्च की सबसे बड़ी कमी इसकी अक्षमता है, खासकर बड़े डाटासेट्स के साथ। इसकी टाइम कॉम्प्लेक्सिटी O(n) होती है, यानी सबसे बुरे हाल में आपको सूची के हर एलिमेंट को जाँचना पड़ सकता है! यदि आप हज़ारों या लाखों प्रविष्टियों से काम कर रहे हैं तो यह चीज़ों को काफी धीमा कर सकती है। हालाँकि, छोटे डाटासेट्स के लिए यह अक्षमता नगण्य हो सकती है।

Python में Linear Search एल्गोरिदम लागू करना

Python में लीनियर सर्च लिखने के दो सामान्य तरीके हैं: iterative विधि और recursive विधि। इन दोनों तरीकों को दिखाने के लिए, पहले बिना डुप्लिकेट्स के 100 संख्याओं का एक सरल डाटासेट बनाते हैं।

numbers = [12, 7, 19, 3, 15, 25, 8, 10, 42, 56, 77, 23, 89, 65, 33, 99, 14, 2, 37, 81,
           48, 64, 22, 91, 6, 40, 59, 87, 28, 53, 74, 9, 16, 39, 71, 93, 54, 32, 61, 27,
           35, 18, 49, 68, 83, 46, 57, 29, 95, 11, 26, 44, 78, 5, 66, 73, 41, 85, 31, 50,
           20, 63, 88, 34, 90, 60, 67, 4, 52, 36, 62, 80, 21, 84, 98, 13, 45, 69, 30, 38,
           47, 17, 92, 55, 70, 76, 82, 24, 43, 1, 100, 58, 96, 75, 97, 94, 86, 72, 51, 79]संचालित द्वारा

Iterative विधि

Iterative अप्रोच शायद लीनियर सर्च को समझने का सबसे आसान तरीका है। आप सूची पर लूप लगाते हैं और हर एलिमेंट की जाँच करते हैं जब तक लक्ष्य न मिल जाए या आप अंत तक न पहुँचें।

सबसे पहले, हम अपना फ़ंक्शन बनाएँगे:

1. हम सूची arr के हर एलिमेंट पर लूप चलाएँगे।

2. हम हर एलिमेंट की तुलना लक्ष्य से करेंगे।

3. यदि मेल मिल जाए, तो हम वह इंडेक्स लौटाएँगे जहाँ लक्ष्य मिला।

4. यदि लक्ष्य न मिले और लूप पूरा हो जाए, तो हम 1 लौटाएँगे ताकि संकेत मिले कि एलिमेंट मौजूद नहीं है।

def linear_search_iterative(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index if the target is found
    return -1  # Return -1 if the target is not foundसंचालित द्वारा

अगला कदम, हम अपने डाटासेट पर फ़ंक्शन चलाएँगे और परिणाम प्रिंट करेंगे:

# Run the function on the numbers list
target = 91
index = linear_search_iterative(numbers, target)

if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found!")संचालित द्वारा

यह कोड चलाने पर, हमें लक्ष्य वैल्यू 23वें एलिमेंट पर मिलती है।

Recursive विधि

Recursive विधि में एक फ़ंक्शन स्वयं को कॉल करता है और सूची में खोज करता है। हर recursive कॉल एक समय में एक एलिमेंट प्रोसेस करता है और फिर अगले पर बढ़ता है। यह तब तक चलता है जब तक लक्ष्य न मिल जाए या सूची का अंत न आ जाए।

आइए अपना recursive फ़ंक्शन बनाएँ:

1. हम पहले एलिमेंट (इंडेक्स 0) की जाँच से शुरू करेंगे।
2. यदि लक्ष्य मेल खाता है, तो हम इंडेक्स लौटाएँगे।
3. यदि लक्ष्य मेल नहीं खाता, तो हम उसी फ़ंक्शन को recursive तरीके से कॉल करेंगे, पर इंडेक्स में 1 जोड़कर ताकि अगला एलिमेंट जाँचा जा सके।
4. रिकर्शन तब तक चलता है जब तक लक्ष्य न मिल जाए या सूची का अंत न आ जाए।

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):  # Base case: we've checked all elements
        return -1
    if arr[index] == target:  # Base case: target found
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive case: check next elementसंचालित द्वारा

हम ऊपर वाला ही कोड इस फ़ंक्शन को चलाने के लिए उपयोग कर सकते हैं और यह हमारे लक्ष्य के लिए वही इंडेक्स लौटाता है: 23।

ध्यान रखें कि यह तरीका अधिक मेमोरी उपयोग करता है क्योंकि हर recursive कॉल कॉल स्टैक में एक नई परत जोड़ती है। यहाँ देखें Understanding Recursive Functions in Python ताकि रिकर्शन को और करीब से समझ सकें।

Time और Space Complexity

किसी एल्गोरिदम की दक्षता का आकलन करने का एक तरीका है उसकी टाइम और स्पेस कॉम्प्लेक्सिटी देखना। अलग-अलग तरीकों से कॉम्प्लेक्सिटी मापने के लिए यह ट्यूटोरियल देखें Analyzing Complexity of Code through Python।

Time complexity

किसी एल्गोरिदम की टाइम कॉम्प्लेक्सिटी बताती है कि इनपुट का आकार बढ़ने पर उसे पूरा होने में लगने वाला समय कैसे बढ़ता है। लीनियर सर्च की टाइम कॉम्प्लेक्सिटी O(n) होती है, जहाँ n सूची में एलिमेंट्स की संख्या है। इसका मतलब है कि सबसे बुरे हाल में, एल्गोरिदम को लक्ष्य ढूँढने से पहले हर एलिमेंट जाँचना पड़ सकता है (या यह निर्धारित करने के लिए कि लक्ष्य सूची में नहीं है)। यह खासकर बड़े डाटासेट्स के लिए काफी अक्षम है। इसलिए लीनियर सर्च छोटे, असॉर्टेड डाटासेट्स में, जहाँ हमें केवल एक बार खोज करनी होती है, सबसे बेहतर काम करता है।

Space complexity

किसी एल्गोरिदम की स्पेस कॉम्प्लेक्सिटी उस मेमोरी की मात्रा का माप है जिसकी आवश्यकता इनपुट के आकार के साथ बढ़ती है। लीनियर सर्च एल्गोरिदम की स्पेस कॉम्प्लेक्सिटी इस पर निर्भर करती है कि हम कौन-सी विधि उपयोग करते हैं। Iterative विधि के लिए, स्पेस कॉम्प्लेक्सिटी O(1) है, यानी इनपुट सूची के आकार से स्वतंत्र रूप से एक स्थिर मात्रा की मेमोरी पर्याप्त है। ऐसा इसलिए क्योंकि iterative संस्करण को इनपुट सूची और वर्तमान इंडेक्स पर नज़र रखने वाले कुछ वेरिएबल्स के अलावा अतिरिक्त मेमोरी नहीं चाहिए।

Recursive विधि के लिए, स्पेस कॉम्प्लेक्सिटी O(n) है, यानी आवश्यक मेमोरी इनपुट सूची के आकार के साथ रैखिक रूप से बढ़ती है। यह recursive फ़ंक्शन कॉल्स के कारण होता है, जो सूची के हर एलिमेंट के लिए कॉल स्टैक में परतें जोड़ते हैं। बड़ी सूची को उन कॉल्स को स्टोर करने के लिए अधिक मेमोरी चाहिए, जिससे recursive अप्रोच स्पेस-इफिशिएंट कम हो जाती है।

Linear Search के वास्तविक-जीवन उपयोग

हालाँकि लीनियर सर्च बड़े डाटासेट्स के लिए सबसे कुशल एल्गोरिदम नहीं है, फिर भी कई परिस्थितियों में इसका व्यावहारिक उपयोग है। आइए देखें कि किन स्थितियों में लीनियर सर्च काम का बेहतरीन औज़ार है।

छोटे डाटासेट्स जहाँ सॉर्ट करना व्यावहारिक नहीं

जब छोटे डाटासेट्स से निपटना हो जिनको सॉर्ट करने में समय या संसाधन लगाना उचित न हो, लीनियर सर्च अक्सर मेरी पहली पसंद होती है। ऐसे मामलों में, लीनियर सर्च की सादगी, डेटा को अधिक जटिल सर्च एल्गोरिदम्स के लिए सॉर्ट करने की ओवरहेड के मुकाबले अधिक दक्ष हो सकती है।

लक्ष्य की पहली उपस्थिति ढूँढना

लीनियर सर्च का एक और सामान्य उपयोग तब है जब आपको किसी लक्ष्य वैल्यू की पहली उपस्थिति ढूँढनी हो। चूँकि लीनियर सर्च सूची में एक-एक एलिमेंट आगे बढ़ता है, यह स्वाभाविक रूप से लक्ष्य की पहली घटना पाता है और उसकी स्थिति लौटाता है। यह खासकर तब उपयोगी है जब आप किसी स्ट्रिंग में किसी कैरेक्टर की पहली उपस्थिति खोज रहे हों।

जब न्यूनतम सेटअप चाहिए

कभी-कभी, लीनियर सर्च की सादगी ही उसे सबसे अच्छा विकल्प बनाती है। उदाहरण के लिए, यदि आप ऐसे डेटा में जल्दी-जल्दी खोज कर रहे हैं जिसे आप दोबारा उपयोग करने की उम्मीद नहीं करते, या आपको तुरंत एक मोटा-मोटी उत्तर चाहिए, तो लीनियर सर्च का न्यूनतम सेटअप आपका समय बचा सकता है।

Linear Search बनाम अन्य सर्च एल्गोरिदम्स

लीनियर सर्च कई सर्च एल्गोरिदम्स में से सिर्फ एक है। आइए दो अन्य सामान्य सर्च एल्गोरिदम्स देखें: बाइनरी सर्च और हैश लुकअप।

Linear search बनाम binary search

बाइनरी सर्च एक एल्गोरिदम है जो सॉर्टेड ऐरे में लक्ष्य वैल्यू की स्थिति खोजने के लिए सर्च इंटरवल को बार-बार आधा करता है। इसकी टाइम कॉम्प्लेक्सिटी O(log n) होती है, जो इसे लीनियर सर्च से कहीं अधिक कुशल बनाती है। हालाँकि, यह केवल सॉर्टेड डेटा पर काम करता है। जब आपका डाटासेट सॉर्टेड हो, तो बाइनरी सर्च लगभग हमेशा बेहतर विकल्प होता है क्योंकि यह हर कदम पर सर्च स्पेस को आधा कर देता है, जिससे तुलना की संख्या बहुत घट जाती है।

लीनियर सर्च उन स्थितियों में अधिक उपयुक्त हो सकता है जहाँ आपका डेटा असॉर्टेड हो, क्योंकि लीनियर सर्च किसी भी डाटासेट पर काम करता है, चाहे वह सॉर्टेड हो या नहीं। हालाँकि, O(n) टाइम कॉम्प्लेक्सिटी के साथ, सॉर्टेड डाटासेट्स पर लीनियर सर्च काफी कम दक्ष होता है।

Linear search बनाम hash lookup

हैश लुकअप एक तरीका है जो हैश टेबल का उपयोग करके किसी एलिमेंट को तेज़ी से ढूँढता है। O(1) टाइम कॉम्प्लेक्सिटी के साथ, यह लीनियर या बाइनरी सर्च दोनों से काफ़ी तेज़ होता है। मगर यह गति एक लागत के साथ आती है: पहले आपको एक हैश टेबल बनानी पड़ती है, जिसके लिए समय और अतिरिक्त मेमोरी दोनों चाहिए। हैश लुकअप तब सबसे अच्छा काम करता है जब आपको बड़े डाटासेट्स में बार-बार खोज करनी हो, ताकि शुरुआती सेटअप समय के साथ वसूल हो जाए।

इसके विपरीत, लीनियर सर्च को किसी सेटअप की ज़रूरत नहीं होती, जिससे यह अधिक सीधा विकल्प बन जाता है। यह तब बेहतर चुनाव है जब आपको केवल एक बार या कुछ ही बार खोज करनी हो, जहाँ हैश टेबल सेटअप करने का अतिरिक्त समय उचित न ठहरे। स्पेस के लिहाज़ से भी लीनियर सर्च अधिक किफायती हो सकता है क्योंकि एल्गोरिदम चलाने के लिए आपको हैश टेबल स्टोर नहीं करनी पड़ती।

आम गलतियाँ और उनसे बचाव

हालाँकि लीनियर सर्च एक सीधे-सादे एल्गोरिदम है, फिर भी कुछ आम गलतियाँ हैं जिनसे सावधान रहना चाहिए।

इटरेशन में off-by-one त्रुटियाँ

लीनियर सर्च लागू करते समय सबसे आम गलतियों में से एक है off-by-one त्रुटि। यह गलत इंडेक्स से इटरेशन शुरू या बंद करने के कारण होती है। यह याद रखना महत्वपूर्ण है कि Python लिस्ट्स zero-indexed होती हैं, यानी पहला एलिमेंट का इंडेक्स 0 होता है। इसे भूल जाने से आप गलती से पहला एलिमेंट छोड़ सकते हैं या एक कदम ज़्यादा इटरेट कर सकते हैं, जिससे गलत परिणाम या एरर हो सकती है।

लौटे गए इंडेक्स को गलत समझना

एक और आम कमी यह समझने में गलती है कि जब लक्ष्य सूची में नहीं मिलता तो फ़ंक्शन क्या लौटाता है। परंपरानुसार, कई सर्च एल्गोरिदम (लीनियर सर्च सहित) -1 लौटाते हैं ताकि संकेत मिले कि लक्ष्य मौजूद नहीं है। हालाँकि, कुछ शुरुआती लोग मान सकते हैं कि यह None, False, या कोई और वैल्यू लौटाएगा, जिससे परिणामों की व्याख्या करते समय भ्रम हो सकता है।

कब लीनियर सर्च का उपयोग न करें

जैसा कि हमने पहले उल्लेख किया, बड़े डाटासेट्स के लिए लीनियर सर्च जल्दी ही अक्षम हो जाता है। इसलिए, इसे छोटे, असॉर्टेड डाटासेट्स या त्वरित, एकबारगी खोजों के लिए ही रखना बेहतर है।

निष्कर्ष

सबसे सीधे-साधे सर्च तरीकों में से एक होने के नाते, लीनियर सर्च सूची के हर एलिमेंट को क्रमवार जाँचता है, जिससे इसे समझना और लागू करना आसान हो जाता है। छोटे डाटासेट्स पर त्वरित, एकबारगी खोजों के लिए, खासकर जब डेटा असॉर्टेड हो, लीनियर सर्च एक भरोसेमंद विकल्प है।

यदि आप सर्च एल्गोरिदम्स में रुचि रखते हैं, तो इस श्रृंखला के मेरे अन्य लेख देखें: Binary Search in Python, Depth-First Search in Python, और Breadth-First Search in Python। आपको यह भी रुचिकर लग सकता है AVL Tree: Complete Guide With Python Implementation और Introduction to Network Analysis in Python जैसे उन्नत विषय।