বাইনারি সার্চ

নির্দেশনা

আপনার কাজ হলো একটি বাইনারি সার্চ অ্যালগরিদম তৈরি করা।

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

অ্যালগরিদমটি দেখতে এমন:

• একটি সাজানো অ্যারের মাঝের এলিমেন্ট খুঁজে সেটিকে আমাদের খোঁজা আইটেমের সাথে তুলনা করুন।
• যদি মাঝের এলিমেন্টটি আমাদের আইটেম হয়, তাহলে আমাদের কাজ শেষ!
• যদি মাঝের এলিমেন্টটি আমাদের আইটেমের চেয়ে বড় হয়, তাহলে আমরা সেই এলিমেন্ট এবং তার পরে থাকা সব এলিমেন্ট বাদ দিতে পারি।
• যদি মাঝের এলিমেন্টটি আমাদের আইটেমের চেয়ে ছোট হয়, তাহলে আমরা সেই এলিমেন্ট এবং তার আগে থাকা সব এলিমেন্ট বাদ দিতে পারি।
• যদি অ্যারেটির প্রতিটি এলিমেন্ট বাদ দেওয়া হয়ে যায়, তাহলে আইটেমটি অ্যারেতে নেই।
• নাহলে, অ্যারেটির যে অংশটি এখনো বাদ দেওয়া হয়নি, তার উপরেই প্রক্রিয়াটি আবার করুন।

এখানে একটি উদাহরণ:

ধরা যাক, নিচের সাজানো অ্যারেতে আমরা 23 সংখ্যাটি খুঁজছি: [4, 8, 12, 16, 23, 28, 32].

• আমরা শুরু করি 23-কে মাঝের এলিমেন্ট 16-এর সাথে তুলনা করে।
• যেহেতু 23, 16-এর চেয়ে বড়, আমরা অ্যারেটির বাম অর্ধেক বাদ দিতে পারি, ফলে আমাদের কাছে থাকে [23, 28, 32].
• এরপর আমরা 23-কে নতুন মাঝের এলিমেন্ট 28-এর সাথে তুলনা করি।
• যেহেতু 23, 28-এর চেয়ে ছোট, আমরা অ্যারেটির ডান অর্ধেক বাদ দিতে পারি: [23].
• আমরা আমাদের আইটেমটি খুঁজে পেয়েছি।

---

সূত্র

Wikipedia