ভূমিকা
আপনি হঠাৎ করেই একদল গণিতবিদের সাক্ষাৎ পেয়ে গেছেন, যাঁরা একইসাথে গায়ক-গীতিকারও। তাঁরা তাঁদের প্রিয় প্রতিটি সংখ্যার জন্য একটি করে গান লিখেছেন, আর আপনি নিশ্চয়ই ভাবতে পারেন, তাঁদের প্রিয় সংখ্যার কোনো শেষ নেই (যেমন 0 বা 73 বা 6174)।
আপনার প্রিয় সংখ্যাটির গানটি শুনতে আপনার কৌতূহল হচ্ছে, কিন্তু এতগুলো গানের ভিড়ে সঠিক গানটি খুঁজে বের করতে বেশ কিছুটা সময় লেগে যেতে পারে।
সৌভাগ্যবশত, তাঁরা তাঁদের গানগুলো শিরোনাম অনুযায়ী সাজিয়ে একটি প্লেলিস্ট তৈরি করেছেন। আর সেই শিরোনাম আসলে সেই সংখ্যাটিই, যে সংখ্যা নিয়ে গানটি লেখা।
আপনি বুঝতে পারেন, শিরোনাম জানা থাকলে বাইনারি সার্চ অ্যালগরিদম ব্যবহার করে দ্রুত গানটি খুঁজে বের করা যায়।
নির্দেশনা
আপনার কাজ হলো একটি বাইনারি সার্চ অ্যালগরিদম বাস্তবায়ন করা।
একটি বাইনারি সার্চ অ্যালগরিদম অ্যারেটিকে বারবার অর্ধেক করে ভাগ করে, আর যে অর্ধেকে আমাদের খোঁজা আইটেমটি থাকে কেবল সেই অর্ধেক ধরে রেখে, অ্যারের মধ্যে একটি আইটেম খুঁজে বের করে।
এটি আমাদের আইটেমটির সম্ভাব্য অবস্থানগুলো দ্রুত কমিয়ে আনতে সাহায্য করে, যতক্ষণ না আমরা সেটি খুঁজে পাই বা সম্ভাব্য সব অবস্থান বাদ দিয়ে ফেলি।
বাইনারি সার্চ কেবল তখনই কাজ করে যখন অ্যারেটি সাজানো থাকে।
অ্যালগরিদমটি দেখতে এমন:
- একটি সাজানো অ্যারের মাঝের এলিমেন্ট খুঁজে বের করুন এবং সেটির সাথে আমাদের খোঁজা আইটেমের তুলনা করুন।
- যদি মাঝের এলিমেন্টটি হয় আমাদের খোঁজা আইটেম, তাহলে আমাদের কাজ শেষ!
- যদি মাঝের এলিমেন্টটি আমাদের আইটেমের চেয়ে বড় হয়, তাহলে আমরা সেই এলিমেন্ট এবং তার পরের সব এলিমেন্ট বাদ দিতে পারি।
- যদি মাঝের এলিমেন্টটি আমাদের আইটেমের চেয়ে ছোট হয়, তাহলে আমরা সেই এলিমেন্ট এবং তার আগের সব এলিমেন্ট বাদ দিতে পারি।
- যদি অ্যারের প্রতিটি এলিমেন্ট বাদ দেওয়া হয়ে যায়, তাহলে আইটেমটি অ্যারেতে নেই।
- অন্যথায়, অ্যারের যে অংশটি এখনো বাদ দেওয়া হয়নি তার উপর একই প্রক্রিয়া পুনরাবৃত্তি করুন।
এখানে একটি উদাহরণ:
ধরা যাক, আমরা নিচের সাজানো অ্যারেতে 23 সংখ্যাটি খুঁজছি: [4, 8, 12, 16, 23, 28, 32].
- আমরা প্রথমে 23-কে মাঝের এলিমেন্ট 16-এর সাথে তুলনা করি।
- যেহেতু 23, 16-এর চেয়ে বড়, তাই আমরা অ্যারের বাম অর্ধেক বাদ দিতে পারি, ফলে আমাদের হাতে থাকে
[23, 28, 32].
- এরপর আমরা 23-কে নতুন মাঝের এলিমেন্ট 28-এর সাথে তুলনা করি।
- যেহেতু 23, 28-এর চেয়ে ছোট, তাই আমরা অ্যারের ডান অর্ধেক বাদ দিতে পারি:
[23].
- আমরা আমাদের আইটেমটি খুঁজে পেয়েছি।
এক্সেপশন মেসেজ
কখনও কখনও এক্সেপশন রেইজ করা প্রয়োজন হয়। এটি করার সময়, এররের উৎস কী তা বোঝানোর জন্য সবসময় একটি অর্থবহ এরর মেসেজ যোগ করা উচিত। এতে আপনার code আরও পাঠযোগ্য হয় এবং debug করতে অনেক সুবিধা হয়। যেসব ক্ষেত্রে আপনি জানেন যে এররের উৎসটি একটি নির্দিষ্ট টাইপের হবে, সেখানে আপনি বিল্ট-ইন এরর টাইপগুলোর যেকোনো একটি রেইজ করা বেছে নিতে পারেন, তবে তবুও একটি অর্থবহ মেসেজ যোগ করা উচিত।
এই নির্দিষ্ট অনুশীলনীতে, দেওয়া মানটি অ্যারের মধ্যে না থাকলে একটি ValueError "থ্রো" করার জন্য আপনাকে raise স্টেটমেন্ট ব্যবহার করতে হবে। টেস্ট পাস করতে হলে আপনাকে exception raise করতে হবে এবং তার সঙ্গে একটি মেসেজও দিতে হবে।
একটি মেসেজ-সহ ValueError রেইজ করতে হলে, মেসেজটি exception টাইপের আর্গুমেন্ট হিসেবে লিখুন:
# example when value is not found in the array.
raise ValueError("value not in array")
