पायथन में लीनियर सर्च के लिए प्रोग्राम लिखें

लीनियर सर्च एक सर्चिंग तकनीक है जिसका उपयोग ऐरे से किसी विशेष वैल्यू को सर्च करने के लिए किया जाता है। यह सबसे सरल सर्चिंग तकनीक है।

इस सर्चिंग तकनीक में,

• सर्च की जाने वाली वैल्यू की तुलना ऐरे के सभी एलिमेंट्स के साथ की जाती है।

• यदि वैल्यू मिल जाती है, तो एलिमेंट का इंडेक्स वापस किया जाता है।

• यदि विशेष एलिमेंट पूरे ऐरे में मौजूद नहीं है, तो -1 या कोई प्रासंगिक स्ट्रिंग मैसेज वापस करें।

स्यूडोकोड

linearSearch(int array[], int value):
    for i = 0 to len(array):
        if array[i] == value:
            Element is Present
    // outside for loop
    Element Not Present // element not found in the whole array

उदाहरण

def linearSearch(arr, value):
    for i in range(len(arr)):
        if arr[i] == value:
            return i
    return -1

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
value = 5
a = linearSearch(array, value)
if a == -1:
    print("Element not present")
else:
    print("Element present at index", a)

आउटपुट

Element present at index 4

टाइम कॉम्प्लेक्सिटी

लीनियर सर्च की सबसे खराब स्थिति की टाइम कॉम्प्लेक्सिटी O(n) है। सबसे खराब स्थिति तब होती है जब एलिमेंट ऐरे के अंतिम इंडेक्स पर मौजूद होता है या बिल्कुल मौजूद नहीं होता।

लीनियर सर्च की सर्वोत्तम स्थिति की टाइम कॉम्प्लेक्सिटी O(1) है। सर्वोत्तम स्थिति तब होती है जब एलिमेंट ऐरे के पहले इंडेक्स पर मौजूद होता है।

बेहतर लीनियर सर्च

लीनियर सर्च की सबसे खराब स्थिति की कॉम्प्लेक्सिटी को O(n/2) तक सुधारा जा सकता है। यह दो पॉइंटर्स, लेफ्ट और राइट का उपयोग करके और एक समय में दो तुलनाएं करके किया जा सकता है, जिससे लीनियर सर्च की सबसे खराब स्थिति की टाइम कॉम्प्लेक्सिटी O(n/2) तक कम हो जाती है।

उदाहरण

def linearSearch(arr, value):
    left = 0
    right = len(arr) - 1
    while left <= right:
        if arr[left] == value:
            return left
        elif arr[right] == value:
            return right
        left += 1
        right -= 1
    return -1

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
value = 10
a = linearSearch(array, value)
if a == -1:
    print("Element not present")
else:
    print("Element present at index", a)

आउटपुट

Element present at index 9

उपरोक्त उदाहरण में, अंतिम इंडेक्स पर मौजूद एलिमेंट पहले इटरेशन में ही मिल जाता है। पहली विधि का उपयोग करके, इस एलिमेंट को ढूंढने में 10 इटरेशन्स लगते।

यदि एलिमेंट नहीं मिलता है, तो सबसे खराब स्थिति की कॉम्प्लेक्सिटी O(n/2) है, क्योंकि दूसरी विधि में कुल इटरेशन्स n/2 हैं।

लीनियर सर्च कितना उपयोगी है?

लीनियर सर्च का शायद ही कभी उपयोग किया जाता है क्योंकि बाइनरी सर्च जैसे बेहतर सर्चिंग एल्गोरिदम हैं जो बेहतर टाइम कॉम्प्लेक्सिटी प्रदान करते हैं। लीनियर सर्च बड़े इनपुट ऐरे के लिए कुशल नहीं है।