বাইসেকশন মেথড বেসিক টিউটোরিয়াল

বাইসেকশন মেথড

আচ্ছা তোমাকে যদি বলা হয় একটা কম্পিউটার প্রোগ্রাম লিখ, যেটা যেকোনো একটি সংখ্যা x  (x>=0)এর বর্গমূল বের করবে , যেটা কে ইংরেজী তে বলে square root. যারা প্রোগ্রামিং ল্যাঙ্গুয়েজ জানে, তাদের কাছে ব্যাপার টা সোজা। কারন প্রায় সব প্রোগ্রামিং ল্যাঙ্গুয়েজ এই sqrt() নামে ফাংশন আছে , যা সহজেই বর্গমূল বের করে দিবে। কিন্তু এখন যদি বলা হয় যে, cubic root/ ³√x অথবা ⁴√x  বের করতে হবে, তখন কি করব? হুম… চিন্তার ব্যাপার। কারন এই রকম কোন built in ফাংশন সাধারন প্রোগ্রামিং ল্যাঙ্গুয়েজ এ নাই! তাইলে উপায় ??

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

২ ৪ ৫ ১১ ১৫ ২০

এখন তোমাকে বলা হল যে, এই সংখ্যা গুলোর মধ্যে ৪ আছে কিনা বলতে হবে। এই সমস্যা সমাধান এর দুইটা উপায়ে আছে,

১। যতোগুলা সংখ্যা দেয়া আছে, সবগুলা একটা একটা করে দেখা যে সংখ্যা টি ৪ কিনা।

২। বাইনারী সার্চ করা

প্রথম উপায়ে টা আসলে সবসময়েই কাজ করে, কিন্তু আমাকে যদি ১০০০০০০ টা সংখ্যা দেয়া হয়, তাহলে এই পদ্ধতি টা অনেক ধীর গতির হবে। সবচেয়ে খারাপ ক্ষেত্রে আমাকে পুরো ১০০০০০০ টা সংখ্যাই দেখতে হবে। Big Oh notation এ যদি ব্যাপার টাকে বলা হয়, তাহলে order হবে O(N) [যেখানে N হচ্ছে কতগুলো সংখ্যা দেয়া হল]।

এইতো গেল প্রথম উপায়।

এইবার আসি, দ্বিতীয় উপায়ে…

বাইনারি সার্চ কি করে? আমরা আগেই জানি যে, আমাদের কে যে সংখ্যা গুলো দেয়া হয়েছে সেগুলো ছোট থেকে বড় এভাবে সাজানো। আর এই শর্ত টা পুরন হলেই বাইনারি সার্চ করা সম্ভব। এখন বাইনারি সার্চ কি করবে জানো? প্রথমে একটা mid value বা মধ্যমা নির্ধারণ করবে , তারপর দেখবে যে সেটা আমি যেই সংখ্যা টা চাচ্ছি সেটা কিনা? যদি না হয়, তাহলে দেখবে যে, মধ্যমা টি আমি যেই সংখ্যাটি চাচ্ছি  , তার থেকে বড় নাকি ছোট। যদি ছোট হয় তাহলে সে শুরু থেকে অই মধ্যমা পর্যন্ত নতুন ভাবে সার্চ চালাবে, আর যদি বড় হয় তাহলে অই মধ্যমা এর পর থেকে শেষ পর্যন্ত নতুন ভাবে সার্চ চালাবে। উদাহরন দেখলে ব্যাপার টা আরো পরিস্কার হবে। আমাদের কে যেই সংখ্যা দেয়া হয়েছে সেগুলো একবার দেখি।

২ ৪ ৫ ১১ ১৫ ২০

এখন আমাকে ৪ খুজতে হবে। আমাকে ৬ টা সংখ্যা দেয়া হয়েছে। এখন প্রথম মধ্যমা টা নির্ধারণ করি। মধ্যমা ১= (১+৬)/২=৩.৫=৩ [স্বাভাবিক সংখ্যায়ে প্রকাশ করা হোল] , প্রথম মধ্যমা টা হচ্ছে ৩য় সংখ্যা টি অর্থাৎ ৫। এখন আমরা চাচ্ছি ৪, পেলাম ৫। হোল না । তাহলে আমাকে আবার সার্চ করতে হবে। কিনতু এখন একটা ব্যাপার দেখ, ৫ > ৪। তাহলে ৫ এর পরে যত সংখ্যা আছে  সবই তাহলে ৪ এর থেকে বড় , কেননা সংখ্যা গুলো ছোট থেকে বড় এভাবে সাজানো। তাহলে আমরা একটা কাজ করতে পারি না! ৫ এর পর যারা আছে তাদের কে আমরা হিশাব থেকে বাদ দিতে পারি না? হুম… অবশ্যই পারি। আমরা এখন দেখব ১ম থেকে ৩য় সংখ্যা এর মাঝে ৪ আছে কিনা। আবার মধ্যমা নির্ধারণ করি। মধ্যমা ২= (১+৩)/২=২। অর্থাৎ ২য় সংখ্যাটি। আর সেটা হচ্ছে ৪। আরি… আমরা ৪ পেয়ে গেছি।

মাত্র ২ ধাপে আমরা ফলাফল পেয়ে গেছি , তাই না? একারনে বাইনারি সার্চ এর অর্ডার O(logn)। উম… ১ম উপায়েও তো ২ ধাপেই ফলাফল পেতাম, তাইলে লাভ টা কি হল? বলছি… তোমাকে যদি ১১ খুজতে দেয়া হয়, তাহলে তুমি কয় ধাপে ফলাফল পাবা ? ৫ ধাপে। কিন্তু বাইনারি সার্চ দিয়ে ২ ধাপেই পেয়ে যাবা। কিভাবে? নিজেই চেষ্টা করে দেখ।

এতক্ষন খালি বাইনারি সার্চ নিয়া বয়ান আর গুনগান ছারলাম। কিন্তু আমার মেইন টপিক তো বাইসেকশন !! সেটার কি হবে? আসছি তাতে……

বাইসেকশন আসলে বাইনারি সার্চ এর ই এক ভাই। বাইনারি সার্চ sorted  sequence এ খুজে বের করে, আর বাইসেকশন সমীকরণ এর মধ্যে খুজে বের করে। তবে এর ও একটা শর্ত আছে, সেটা হচ্ছে সমীকরণ টিকে x এর সাপেক্ষে ঊর্ধ্বমুখী অথবা নিম্নমুখি হতে হবে। যেমনঃ y=x, y=x*x ইত্যাদি। এখানে x এর মান যত বারাচ্ছি y এর মান তত বারতেছে অথবা এর উল্টো টা । এরকম ক্ষেত্রে বাইসেকশন করা যাবে। কারন দেখ যে,  ব্যাপার টা কিন্তু ছোট থেকে বড় ভাবে সাজানো সংখ্যা এর মতোই, তাই না?

আমরা তো বাইনারি সার্চ কি তা জানি, এখন একি ভাবে বাইসেকশন এ কি হয় তা দেখব। ধরো আমরা বের করতে চাই ১৬ এর বর্গ মুল । বর্গমূল এর সাধারন সমীকরণ কি? y=root(x) . এখানে x=16 বসালে আমরা y এর মান ৪ পাবো। এই সমীকরণ টা কিন্তু ঊর্ধ্বমুখী [increasing] । তুমি যথাক্রমে, x=4, x=9, x=16 বসাও । দেখবে y এর মান বেড়ে যাচ্ছে।

যাই হোক, এখন আমরা  এই সমীকরণ টাকে এভাবে লিখতে পারি

y=x*x

কিভাবে, আমি যদি x=4 বসাই তাহলে কি পাচ্ছি y=16. তাহলে ব্যাপার টা একি দাঁড়াচ্ছে। শুধু চলক গুলো [variable] পরিবর্তন করলাম এই যা।

এখন আমরা বাইসেকশন করার জন্য লিমিট ঠিক করব। আগে বাইনারি সার্চ করার জন্য আমাদের লিমিট ছিল ১ থেকে যতোটি সংখ্যা দেয়া হয়েছে। এবার লিমিট হচ্ছে ০ থেকে আমাদের কে যতো সংখ্যা এর বর্গমূল বের করতে হবে।

তো শুরু করা যাক, আগের মত করে মধ্যমা বের করি প্রথমে,

মধ্যমা ১= (০+১৬)/২=৮। এখন ৮ টাকে আমাদের সমীকরণ টাতে বসাই, y=64 পাই যা ১৬ থেকে অনেক বড়। তাহলে আমাদের লিমিট আরেকটু কমাইতে হবে। নতুন লিমিট ০ থেকে ৮। নতুন মধ্যমা বের করি, মধ্যমা ২= (০+৮)/২=৪ ।  সমীকরণ টাতে ৪ বসাই, কি পাচ্ছি ? y=16 তাই না ? যা আমরা যেই সংখ্যা এর বর্গমূল চেয়েছিলাম সেটাই। তাহলে ১৬ এর বর্গমূল ৪। কাজ শেষ। সহজ জিনিশ তাই না ? এখন  বদলে তুমি  যদি x*x*x , x*x*x*x*x বসাও তাহলে কিন্তু তুমি  ও বের করে ফেলতে পারবে। ACM Programming Contest, Programming/ Algorithmic Problem solving এ বাইনারি সার্চ আর বাইসেকশন অনেক কাজে লাগে। পরে সেটা নিয়ে আলোচনা করব আরেক দিন [যদি আপনাদের এই লেখা ভালো লাগে 😉 ]। এবার বাইনারি সার্চ এবং বাইসেকশন এর c++ code দেখবো। নিচের লিঙ্ক গুলোতে ক্লিক করো।

বাইনারি সার্চ : http://ideone.com/iza80 , http://pastie.org/8427581

বাইসেকশন: http://ideone.com/oQEap , http://pastie.org/8427578

প্রব্লেমঃ UVA 10341 (http://uva.onlinejudge.org/external/103/10341.html)

[ নোট : বাইসেকশন কোড এ দশমিক সংখ্যা নিয়ে কাজ করার জন্য কিছু কাজ করা হয়েছে, না বুঝে থাকলে অবশ্যই জিজ্ঞাশা করতে হবে J ]

[ নোট : যদি কোন কিছু বুঝতে সমস্যা হয় তবে, মন্তব্য এর স্থানে জিজ্ঞাসা করুন, অথবা আমাকে মেইল করুনঃ faiyaz26 [at] gmail [dot] com এ ]