পাইথনে লিনিয়ার সার্চের জন্য একটি প্রোগ্রাম লিখুন

লিনিয়ার সার্চ হল একটি অনুসন্ধান কৌশল যা একটি অ্যারে থেকে কিছু নির্দিষ্ট মান অনুসন্ধান করার জন্য। এটি সবচেয়ে সহজ অনুসন্ধান কৌশল।

এই অনুসন্ধান কৌশলে,

• যে মান অনুসন্ধান করা হবে তা অ্যারের সমস্ত উপাদানের সাথে তুলনা করা হয়।

• মান পাওয়া গেলে, উপাদানের সূচী প্রদান করা হয়।

• যদি নির্দিষ্ট উপাদানটি অ্যারে জুড়ে উপস্থিত না থাকে, তাহলে -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।

লিনিয়ার সার্চ কতটা দরকারী?

রৈখিক অনুসন্ধান খুব কমই ব্যবহৃত হয় কারণ বাইনারি অনুসন্ধানের মতো আরও ভাল অনুসন্ধানের অ্যালগরিদম রয়েছে যা আরও ভাল সময় জটিলতা প্রদান করে। রৈখিক অনুসন্ধান বড় ইনপুট অ্যারের জন্য দক্ষ নয়৷