বাইনারি সার্চ ইমপ্লিমেন্ট

হাবলু দা’র এক সিনিয়র ভাই তাকে একটা প্রাইম নাম্বারের অর্ডারড/সর্টেড লিস্ট হাতে ধরাই দিয়ে বলল এইটা বাইনারি সার্চ এলগোরিদম ব্যবহার সল্ভ করে দাও। আহা হাবলু দা সেটাকে হাতে পেয়েই লুতুপুতু ভাব নিয়ে মুচকি হাসি দিতে লাগলো। হাবলু দা অবশ্য ২টা কারণে হাসি আটকাতে পারতেছিলেন না। ১) প্রাইম নাম্বারের লিস্টটি অলরেডি সর্টেড। ২) বাইনারি সার্চতো তিনি কয়েকশতবার প্রাকটিস করেছেন!এবার কাহিনী শুরু বড় ভাই মুচকি হাসি দিয়ে বললেন আরে দাড়াও এতো খুশি হওয়ার কিছু হয়নি এখনো। সমস্যা সম্পুর্ন বর্ননা করি তারপর না হয় অট্টহাসি দিও! এই কথা শোনার পর হাবলু দা’র মনের ভিতরে কিঞ্চিৎ ভয় ঢুকে গেছে। আহারে আজকে কপালে বুঝি শনি আছে ভেবে ভেবে হাবলু দা চিন্তিত হয়ে পরলেন। আর ঐ দিকে বড় ভাই তার সমস্যার একটা নোট রেডি করতেছেন।

নোট তৈরি শেষে এবার তিনি হাবলু দা’কে ডেকে বললেন শোন সমস্যাটা খুব বেশী জঠিল কিছু না। খুবই সিম্পল তবে যদি তুমি সিম্পলভাবে চিন্তা করতে পারবো তাহলেই তুমি তুড়ি মেড়ে সল্ভ করতে পারবা। উহা শুনে হাবলুর দা’র তারই অজান্তে ফুড়ুৎ করে একটা আনন্দের হাসি দিয়ে ফেললেন। হাসিটার কারণ আমি তখনো বুঝিনি তবে এতোটুকু বুঝতে পেরেছিলাম যেকোন সমস্যার সমাধান করতে পারার মধ্যে একটা পৈশাচিক আনন্দও আছে।

এবার বড় ভাই হাবলু দা’কে সমস্যাটা বুঝিয়ে দিলেন এভাবেঃ

সমস্যাঃ ধর আমার একটা সর্টেড/অর্ডারড প্রাইম নাম্বারের লিস্ট আছে এখন আমি আমার ইচ্ছা মতো যেখনো একটা নাম্বার ইনপুট দিয়ে দেখতে চাই সেটি প্রাইম নাম্বার কিনা এবং যদি প্রাইম নাম্বার হয় তাহলে তার সামনে আরো কতোটি প্রাইম নাম্বার আছে তার একটা হিসাব যেন আমি জানতে পাই।

সমস্যাটি শোনার পর হাবলু দা প্রায় ৩০ সেকেন্ডের মতো চুপ করে থেকে তারপর বড় ভাইকে বললেন আমার কিছু প্রশ্নও আছে! বড় ভাই সানন্দে বললেন অবশ্যই! বল কি জানতে চাও?

আউটপুট কিভাবে দেখতে চাচ্ছেন? আউটপুট কি বুলিয়ানে দেখাতে হবে?

প্রশ্ন শোনার পর বড় ভাই তাকে বললেন, তুমি আউটপুট দেখাবা হচ্ছে কথায় যেমনঃ ৬৭ হচ্ছে প্রাইম নাম্বার এবং তার আগে এন সংখ্যক প্রাইম নাম্বার আছে। অন্যথায় দেখাবা ৬৭ প্রাইম নাম্বার নয়।

তারপর হাবলু দা বড় ভাইকে বললেন আচ্ছা ঠিক আছে আমি একটা কোল্ড কফি পান করে এসেই সমস্যা সমাধানে বসে যাবো। আমিতো আবার নাছোড় বান্দা তাই হাবলু দা’র পিছে পিছে চলে গেলাম। হাজারো হউক কোল্ড কফি বলে কথা 😛

কফি শেষে হাবলু দা তার টেবিলে বসে খাতা, পেন্সিল নিয়ে কি যেনো নোট করতেছেন। আমি আবার চুপচাপ থাকার ছেলে নই তাই জিজ্ঞাসা করেই ফেললাম আচ্ছা দাদা আপনি সমস্যা সমাধান করবেন কম্পিউটারে পেন্সিল, খাটা নিয়ে কি লিখতে বসলেন? হাবলু দা একটু রাগা রাগা ভাবে বললেন এখন বিরক্ত কইরোনা পরে বুঝাবোনি। আমিও ভয়ে গুটিস্যুটি হয়ে চুপটি করে করে পাশে বসে রইলাম।

পাশে বসে থেকে দেখতেছি হাবলু দা তার খাটায় লিখে রেখেছেনঃ

1) Let min_num = 0 and max_num = n-1

2) Compute the guess as the average of max_num and min_num and make sure it is an integer result.

3) If primes_list[guess] equals target, then stop. Yes found it! Return the result.

4) If the guess was too low, that is, primes_list[guess] < target, then set min_num = guess + 1.

5) Otherwise, the guess was too high. Set max_num = guess – 1.

6) Go back to step 2

সমাধানঃ

আউটপুটঃ