ভূমিকা
আপনি হঠাৎ করেই একদল গণিতবিদের সাক্ষাৎ পেয়ে গেছেন, যাঁরা একইসাথে গায়ক-গীতিকারও। তাঁরা তাঁদের প্রিয় প্রতিটি সংখ্যার জন্য একটি করে গান লিখেছেন, আর আপনি নিশ্চয়ই ভাবতে পারেন, তাঁদের প্রিয় সংখ্যার কোনো শেষ নেই (যেমন 0 বা 73 বা 6174)।
আপনার প্রিয় সংখ্যাটির গানটি শুনতে আপনার কৌতূহল হচ্ছে, কিন্তু এতগুলো গানের ভিড়ে সঠিক গানটি খুঁজে বের করতে বেশ কিছুটা সময় লেগে যেতে পারে।
সৌভাগ্যবশত, তাঁরা তাঁদের গানগুলো শিরোনাম অনুযায়ী সাজিয়ে একটি প্লেলিস্ট তৈরি করেছেন। আর সেই শিরোনাম আসলে সেই সংখ্যাটিই, যে সংখ্যা নিয়ে গানটি লেখা।
আপনি বুঝতে পারেন, শিরোনাম জানা থাকলে বাইনারি সার্চ অ্যালগরিদম ব্যবহার করে দ্রুত গানটি খুঁজে বের করা যায়।
নির্দেশনা
আপনার কাজ হলো একটি বাইনারি সার্চ অ্যালগরিদম বাস্তবায়ন করা।
একটি বাইনারি সার্চ অ্যালগরিদম অ্যারেটিকে বারবার অর্ধেক করে ভাগ করে, আর যে অর্ধেকে আমাদের খোঁজা আইটেমটি থাকে কেবল সেই অর্ধেক ধরে রেখে, অ্যারের মধ্যে একটি আইটেম খুঁজে বের করে।
এটি আমাদের আইটেমটির সম্ভাব্য অবস্থানগুলো দ্রুত কমিয়ে আনতে সাহায্য করে, যতক্ষণ না আমরা সেটি খুঁজে পাই বা সম্ভাব্য সব অবস্থান বাদ দিয়ে ফেলি।
বাইনারি সার্চ কেবল তখনই কাজ করে যখন অ্যারেটি সাজানো থাকে।
অ্যালগরিদমটি দেখতে এমন:
- একটি সাজানো অ্যারের মাঝের এলিমেন্ট খুঁজে বের করুন এবং সেটির সাথে আমাদের খোঁজা আইটেমের তুলনা করুন।
- যদি মাঝের এলিমেন্টটি হয় আমাদের খোঁজা আইটেম, তাহলে আমাদের কাজ শেষ!
- যদি মাঝের এলিমেন্টটি আমাদের আইটেমের চেয়ে বড় হয়, তাহলে আমরা সেই এলিমেন্ট এবং তার পরের সব এলিমেন্ট বাদ দিতে পারি।
- যদি মাঝের এলিমেন্টটি আমাদের আইটেমের চেয়ে ছোট হয়, তাহলে আমরা সেই এলিমেন্ট এবং তার আগের সব এলিমেন্ট বাদ দিতে পারি।
- যদি অ্যারের প্রতিটি এলিমেন্ট বাদ দেওয়া হয়ে যায়, তাহলে আইটেমটি অ্যারেতে নেই।
- অন্যথায়, অ্যারের যে অংশটি এখনো বাদ দেওয়া হয়নি তার উপর একই প্রক্রিয়া পুনরাবৃত্তি করুন।
এখানে একটি উদাহরণ:
ধরা যাক, আমরা নিচের সাজানো অ্যারেতে 23 সংখ্যাটি খুঁজছি: [4, 8, 12, 16, 23, 28, 32].
- আমরা প্রথমে 23-কে মাঝের এলিমেন্ট 16-এর সাথে তুলনা করি।
- যেহেতু 23, 16-এর চেয়ে বড়, তাই আমরা অ্যারের বাম অর্ধেক বাদ দিতে পারি, ফলে আমাদের হাতে থাকে
[23, 28, 32].
- এরপর আমরা 23-কে নতুন মাঝের এলিমেন্ট 28-এর সাথে তুলনা করি।
- যেহেতু 23, 28-এর চেয়ে ছোট, তাই আমরা অ্যারের ডান অর্ধেক বাদ দিতে পারি:
[23].
- আমরা আমাদের আইটেমটি খুঁজে পেয়েছি।
নির্দেশাবলির সংযোজন
সীমাবদ্ধতা
Rust-এর স্ট্যান্ডার্ড লাইব্রেরিতেই আগে থেকেই একটি
binary search function রয়েছে।
এই অনুশীলনীর জন্য এই ফাংশনটি ব্যবহার করা উচিত নয়, বরং এর বদলে অন্য সাধারণ উপকরণগুলোই ব্যবহার করুন।
বোনাস পয়েন্টের জন্য
আপনার টেস্টগুলো কি পাস হয়েছে আর কোড কি পরিষ্কার হয়েছে? আপনি চাইলে আরও কিছু জিনিস চেষ্টা করে দেখতে পারেন।
- বর্তমানে আপনার find ফাংশনটি সম্ভবত শুধু সংখ্যার স্লাইসের জন্য কাজ করবে, কিন্তু Rust-এর টাইপ সিস্টেম যথেষ্ট নমনীয় যে এমন একটি find ফাংশন তৈরি করা যায়, যা এমন সব স্লাইসে কাজ করবে যেগুলোর এলিমেন্টগুলোকে ক্রমানুসারে সাজানো যায়।
- এর সঙ্গে এই find ফাংশনটি শুধু স্লাইসেই নয়, একই সঙ্গে Vec বা Array-এও কাজ করতে পারে।
বোনাস টেস্টগুলো চালাতে #[ignore] ফ্ল্যাগটি সরিয়ে নিন এবং generic ফিচার দিয়ে টেস্টগুলো চালান, এভাবে:
$ cargo test --features generic
তারপর অনুগ্রহ করে সাবমিশনের একটি কমেন্টে আপনার মতামত জানান। এই পরীক্ষা-নিরীক্ষা কি কোডকে আরও ভালো করেছে? নাকি খারাপ? এটি থেকে আপনি কি কিছু শিখতে পেরেছেন?
