পাইথনে বাইনারি অনুসন্ধান ব্যাখ্যা করুন

বাইনারি অনুসন্ধান একটি অনুসন্ধান অ্যালগরিদম যা একটি সাজানো অ্যারে থেকে একটি উপাদান অনুসন্ধান করতে ব্যবহৃত হয়। এটি একটি সাজানো বিন্যাস থেকে অনুসন্ধান করতে ব্যবহার করা যাবে না. বাইনারি অনুসন্ধান একটি দক্ষ অ্যালগরিদম এবং সময়ের জটিলতার ক্ষেত্রে লিনিয়ার অনুসন্ধানের চেয়ে ভাল৷

রৈখিক অনুসন্ধানের সময় জটিলতা হল O(n)। যেখানে বাইনারি অনুসন্ধানের সময় জটিলতা হল O(log n)। তাই, বাইনারি অনুসন্ধান দক্ষ এবং দ্রুত-সার্চিং অ্যালগরিদম কিন্তু শুধুমাত্র সাজানো অ্যারে থেকে অনুসন্ধানের জন্য ব্যবহার করা যেতে পারে।

বাইনারি অনুসন্ধান কিভাবে কাজ করে?

বাইনারি অনুসন্ধানের পিছনে মূল ধারণাটি হল যে অ্যারের সমস্ত উপাদানের সাথে প্রয়োজনীয় উপাদানের তুলনা করার পরিবর্তে, আমরা প্রয়োজনীয় উপাদানটিকে অ্যারের মধ্যম উপাদানের সাথে তুলনা করব। এটি যদি আমরা খুঁজছি এমন উপাদান হিসাবে পরিণত হয়, আমরা সফলভাবে অনুসন্ধানটি সম্পন্ন করেছি। অন্যথায়, আমরা যে এলিমেন্টটি খুঁজছি সেটি মধ্যম এলিমেন্টের থেকে কম হলে, এটা নিশ্চিত যে এলিমেন্টটি অ্যারের প্রথম বা বাম অর্ধে রয়েছে, যেহেতু অ্যারে সাজানো হয়েছে। একইভাবে, যদি আমরা যে উপাদানটি খুঁজছি সেটি মধ্যম উপাদানের চেয়ে বড় হয়, তাহলে নিশ্চিত যে উপাদানটি অ্যারের দ্বিতীয়ার্ধে রয়েছে।

এইভাবে, বাইনারি অনুসন্ধান ক্রমাগত অ্যারেকে অর্ধেক কমিয়ে দেয়। আমরা যে উপাদানটি খুঁজছি তা না পাওয়া পর্যন্ত উপরের প্রক্রিয়াটি অ্যারের নির্বাচিত অর্ধেকের উপর পুনরাবৃত্তিমূলকভাবে প্রয়োগ করা হয়৷

আমরা অ্যারের শেষ সূচকের সমান বাম সূচক 0 এবং ডান সূচক দিয়ে অনুসন্ধান শুরু করব। মধ্যম উপাদান সূচক (মধ্য) গণনা করা হয় যা 2 দ্বারা বিভক্ত বাম এবং ডান সূচকের যোগফল। যদি প্রয়োজনীয় উপাদানটি মধ্যম উপাদানের চেয়ে কম হয়, তবে ডান সূচকটি মধ্য-1 এ পরিবর্তন করা হয়, যার মানে আমরা এখন করব শুধুমাত্র অ্যারের প্রথমার্ধের দিকে তাকান। একইভাবে, যদি প্রয়োজনীয় উপাদানটি মধ্যম উপাদানের চেয়ে বড় হয়, তাহলে বাম সূচকটি মধ্য+1-এ পরিবর্তিত হয়, যার মানে আমরা এখন কেবলমাত্র অ্যারের দ্বিতীয়ার্ধের দিকে তাকাব। আমরা নির্বাচিত অ্যারের অর্ধেকের জন্য উপরের প্রক্রিয়াটি পুনরাবৃত্তি করব।

এলিমেন্ট অ্যারেতে না থাকলে আমরা কিভাবে জানব?

আরও অনুসন্ধান বন্ধ করার জন্য আমাদের কিছু শর্ত থাকা দরকার যা নির্দেশ করবে যে উপাদানটি অ্যারেতে উপস্থিত নেই। যতক্ষণ বাম সূচকটি ডান সূচকের চেয়ে কম বা সমান হয় ততক্ষণ আমরা অ্যারেতে উপাদানটির জন্য পুনরাবৃত্তভাবে অনুসন্ধান করব। একবার এই শর্তটি মিথ্যা হয়ে গেলে এবং আমরা এখনও উপাদানটি খুঁজে পাইনি, এর মানে হল যে উপাদানটি অ্যারেতে উপস্থিত নেই৷

উদাহরণ

চলুন নিচের সাজানো অ্যারে নেওয়া যাক এবং আমাদের এলিমেন্ট 6 সার্চ করতে হবে।

L=0 H=8 মিড=4

6<10, তাই প্রথম অর্ধেক নিন।

H=Mid-1

L=0 H=3 মিড=1

6>5, তাই দ্বিতীয়ার্ধ বেছে নিন।

L=Mid+1

L=2 H=3 মিড=2

6==6, একটি উপাদান পাওয়া গেছে

তাই সূচক 2 এ উপাদান 6 পাওয়া যায়।

বাস্তবায়ন

একটি প্রদত্ত সাজানো অ্যারে থেকে, একটি প্রয়োজনীয় উপাদান অনুসন্ধান করুন এবং যদি অ্যারেটিতে উপাদানটি উপস্থিত থাকে তবে তার সূচকটি প্রিন্ট করুন। উপাদান উপস্থিত না থাকলে, প্রিন্ট -1.

বাইনারি অনুসন্ধান বাস্তবায়নের জন্য কোড নীচে দেওয়া হয়েছে৷

উদাহরণ

def binary_search(arr,x):
   l=0
   r=len(arr)-1
   while(l<=r):
      mid=(l+r)//2
      if(arr[mid]==x):
         return mid
      elif(x<arr[mid]):
         r=mid-1
      elif(x>arr[mid]):
         l=mid+1
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
a=7
print(binary_search(array,a))
b=15
print(binary_search(array,b))

আউটপুট

6
-1

উপাদান 7 সূচক 6 এ উপস্থিত।

এলিমেন্ট 15 অ্যারেতে উপস্থিত নেই, তাই -1 মুদ্রিত হয়।