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

নির্দেশনা

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

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

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

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

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

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

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

পরিশিষ্ট

Clojure ট্র্যাকের এই অনুশীলনীর জন্য, টেস্টগুলো যেমনটি নির্দেশ করে, আপনি ধরে নিতে পারেন যে ইনপুটটি একটি ভেক্টর।

---

সূত্র

Wikipedia