पायथन में रैखिक खोज के लिए एक कार्यक्रम लिखें

रैखिक खोज एक सरणी से कुछ विशेष मान खोजने के लिए एक खोज तकनीक है। यह सबसे सरल खोज तकनीक है।

इस खोज तकनीक में,

• खोजे जाने वाले मान की तुलना सरणी के सभी तत्वों से की जाती है।

• यदि मान पाया जाता है, तो तत्व की अनुक्रमणिका वापस कर दी जाती है।

• यदि विशेष तत्व पूरे सरणी में मौजूद नहीं है, तो -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(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 है।

रैखिक खोज कितनी उपयोगी है?

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