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

নির্দেশনা

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

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

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

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

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

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

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

ইঙ্গিত

Haskell-এ নানা ধরনের অ্যারের সমর্থন আছে। এই অনুশীলনীতে Data.Array থেকে নেওয়া ইমিউটেবল, বক্সড ও নন-স্ট্রিক্ট অ্যারে ব্যবহার করা হয়েছে। এই অ্যারেগুলোর ব্যবহার সম্পর্কে আরও পড়তে পারেন:

• A Gentle Introduction to Haskell: Arrays
• Data.Array নিয়ে ডকুমেন্টেশন

এই অনুশীলনীর একটি ঐচ্ছিক সম্প্রসারণ হিসেবে, find ফাংশনটি যেন যেকোনো সীমার অ্যারে নিয়েও কাজ করে, সেভাবে বানানোর চেষ্টা করে দেখুন, যেমন এমন অ্যারে, যাদের প্রথম ইনডেক্সটি 0 না-ও হতে পারে।

---

সূত্র

Wikipedia