একেবারেই সাধারন কথা বার্তা
এই পর্বে আমরা কম্পিউটার সাইন্সের অত্যন্ত জনপ্রিয় এবং মৌলিক একটি এলগোরিদম নিয়ে আলোচনা করবো, যার নাম বাইনারি সার্চ! কম্পিউটার সাইন্সের বিভিন্ন শাখায় বাইনারি সার্চের ব্যাপক ব্যবহার রয়েছে। ভূমিকা দিয়ে সময় নষ্ট না করে চল একটু শিখে ফেলার চেষ্টা করি বাইনারি সার্চের সবচাইতে সাদামাটা রূপটি!
এই এলগোরিদম শিখার জন্য যা যা জানা থাকতেই হবেঃ
- array এর ব্যাসিক ধারনা থাকতে হবে।
- loop চালাতে পারতে হবে।
প্রথমে একটি ক্ষেত্রের এর কথা বলে নেই, যেটাতে আমরা বাইনারি সার্চ এপ্লাই করতে পারব। ধর তোমাকে integer -এর একটি sorted array দেওয়া আছে। /* সর্টেড না থাকলে সেটা সর্ট করে নিব। */ sorted array বলতে বোঝায়, array এর উপাদান গুলো increasing ( ছোট থেকে বড় হচ্ছে এমন ধারা) অথবা decreasing (বড় থেকে ছোট হচ্ছে এমন ধারা) অর্ডারে আছে। আমরা আমাদের সমস্যায় array-এর উপাদান গুলো increasing অর্ডারে আছে ধরে নিয়ে আলোচনা চালিয়ে যাবো। যেমন নিচের অ্যারেটিতে উপাদান গুলো sorted এবং তারা increasing অর্ডারে আছে।
দেখেই বোঝা যাচ্ছে এই array -তে ৯ টা উপাদান আছে। আর তুমি তো জানোই array -এর ইন্ডেক্স ০ থেকে শুরু হয় তাই এই array-এর শেষ ইন্ডেক্স হবে ৮। এখন তোমাকে একটা সংখ্যা দিয়ে বলবে সংখ্যাটি array-টিতে আছে কিনা। যদি থাকে তবে কত নাম্বার ইন্ডেক্সে আছে। প্রবলেম দেখার পর প্রথমেই যে জিনিষটা মাথায় আসে, তা হল, সমস্ত array -টাতে লুপ চালিয়ে একটি একটি করে চেক করে দেখা উপাদান টা আছে নাকি নাই। কোডটা সি তে দেখতে এমন হবে ………
position = -1 ;
for( index = 0; index < n; index++ ) { /*০ থেকে n এর আগ পর্যন্ত চেক করব ,
n হচ্ছে array -এর উপদান সংখ্যা */
if(array[index] == x) { /* এখানে যদি এর সমান কোন উপাদান পেয়ে যাই ইন্ডেক্স
এর মান position এ রাখব , এবং যেহেতু এক্স পেয়ে গেছি
খুজা খুজি বন্ধ করে দিব । */
position = index;
break;
}
}
if( position != -1) printf(“%d is present in %th index of given array\n ”,x,position);
/* কারন position , -1 দিয়ে ইনিশিয়ালাইজ করা হয়েছিল
যদি array তে x ঊপাদান টি থাকে তবে পজিশন এর মান আর
-1 থাকবে না । */
else printf(“%d is not present in given array\n”,x);
/* কোড রান করতে সমস্যা হতে পারে, সেক্ষেত্রে বাংলাতে লেখা কমেন্ট গুলো ডিলিট করে দিও। */
উপরের কোডটা দেখে বুঝাই যাচ্ছে যে আমরা সর্টেড array বৈশিষ্ট্য ব্যবহার করছি না । অর্থাৎ array টা যদি সর্টেড না থাকে তাহলেও এই কোড দিয়ে কাজ করা যাবে । এইভাবে কোন উপাদান খুজাকে বলে linear search।
এখন কোন একটা এলগোরিদম লিখার আগে অবশ্যই এনালাইজ করতে হবে এর টাইম কমপ্লেক্সিটি কেমন হবে (এটা খুবই জরুরি)। লিনিয়ার সার্চ এর জন্য সবচেয়ে খারাপ কেসে [ উপাদানটি যদি array -তে না থাকে ] লুপ n সংখ্যক বার ঘুরবে, তাই লিনিয়ার সার্চ এর টাইম কমপ্লেক্সিটি হবে O(n) [এটা এভাবে পড়তে হয় – “Big O of n”] ।
এখন আমরা চেষ্টা করে দেখি এর টাইম কমপ্লেক্সিটি আরও কমানো যায় কিনা ।
তাহলে চল শুরু করা যাক।
বাইনারি সার্চের শুরু এখানেই
আগের উদাহন আরেকবার নেওয়া যাক।
মনে করি এই array -তে x=47 সংখ্যাটি আছে কিনা খুজতে হবে , আর আমারা জানি array -টা সর্টেড । /* সর্টেড না থাকলে সেটা সর্ট করে নিব। */
প্রথমেই আমরা array-এর মিড পয়েন্ট বের করব। এখন array -এর মিড পয়েন্টে যে উপাদান আছে তার সাথে x এর তুলনা করব, যদি সমান হয়ে যায় তাহলে তো কেল্লা ফতে! আমরা পজিশন পেয়ে গেলাম। কিন্তু যদি সমান না হয়, তখন কি হবে?
সমান না হলে মিড পয়েন্টের উপাদানটি অবশ্যই x থেকে ছোট কিংবা বড় হবে [“হতেই হবে” কারন এর বাইরে তো আর কিছু নেই]। উপরের array -তে মিড পয়েন্টের উপাদানটি 36 [ ইন্ডেক্স 4]।
নিঃসন্দেহে 36, x-এর চেয়ে ছোট। এখন যেহেতু বলা আছে array -টা সর্টেড তাহলে ইন্ডেক্স 0, 1, 2 , 3 এর উপাদান গুলো অবশ্যই 36 এর চাইতে ছোট হবে ( তা না হলে তো আর অ্যারেটা সর্টেড হল না )। তাই 36 এর আগে x এর মান থাকার কোন সম্ভাবনাই নেই, কিন্তু 36 এর পর অর্থাৎ ইন্ডেক্স 5 , 6 , 7 বা 8 এ থাকার সম্ভাবনা আছে [ সম্ভাবনা আছে বলছি কারন আমরা জানি না সংখ্যাটি array -তে আছে নাকি নাই ]। এখন যেই অংশে থাকার বিন্দু মাত্র সম্ভাবনা নেই, সেই অংশে x এর মান খুজতে যাওয়া বোকামি। আমরা প্রোগ্রামাররা যথেস্ট চালাক, তাই আমরা ওই অংশ বাদ দিয়ে চিন্তা করব। আর যেহেতু x, 36-এর সমান নয়, সেটাও চিন্তার বাইরে রাখব।
এবার আমাদের কাছে 5 থেকে 8 ইন্ডেক্স পর্যন্ত উপাদান আছে যেখানে আমরা x কে খুজব। এখন আমরা আবার এই চারটি উপাদান এর মিড পয়েন্ট বের করব উপাদানটিকে দেখব x এর সমান কি না [এখন যেহেতু ইন্ডেক্স 5-8 পর্যন্ত্ জোড় সংখ্যক উপাদান বাকি তাই 6 বা 7 যেকোনো একটা কে মিড পয়েন্ট ধরলেই হবে, আমরা 6 কে মিড ধরে এগুতে থাকি।]
এখন মাঝখানের উপাদান 63, এটি x এর সমান না এবং x থেকে বড় । 63 এর ডান দিকে x থাকার কোন সম্ভাবনা নেই, তাই ৬৩ সহ পরের গুলা বাদ দিয়ে দেই।
এখন বাকি আছে ইন্ডেক্স 5 এর উপাদান, যেহেতু একটা বাকি তাই সেটাকেই মিড পয়েন্ট ধরব ।
এখন এটাকে x এর সাথে তুলনা করি। দুইটা সমান, তাই আমরা আমাদের কাঙ্খিত পজিশন পেয়ে গেছি। বাইনারি সার্চের কাজ এখানেই শেষ ।
এখন উপরের ঘটনাকে কোডে ইমপ্লিমেন্ট করতে পারলেই আমাদের কাজ শেষ ।
চল এখন C তে এর কোডটা দেখি
int main()
{
int ara[9] = { 2, 6, 13 , 21 , 36 , 47, 63 , 81 , 97 };
int x = 2; /* এই বেটাকেই অ্যারেতে খুজব */
int First_P = 0; /* প্রথম ইন্ডেক্স */
int Last_P = 9; /* শেষ ইন্ডেক্স */
int Pos_x = -1; /* x এর পজিশন Pos_x এ রাখব , যদি X খুজে না পাই
তবে Pos_x এর মান -1 থেকে যাবে । */
while( First_P <= Last_P ) /* ১ম ইন্ডেক্স যদি শেষটা থেকে বড় হয়ে যায় ,
সেটা দিয়ে আসলে ভ্যালিড কিছু বুঝাবে না , যদি বলি শুরুর
ইন্ডেক্স ৪ শেষ ইন্ডেক্স ১ সেটা দিয়ে তুমি কি বুঝবে ? আমার
হাতে কয়টা উপাদান আছে ? আসলে আমার হাতে কিছু নেই ,
যেহেতু আমার কাছে আর উপাদান নেই তাই আমি লুপ ব্রেক করে
খুজা খুজি বন্ধ করে দিব । প্রথম আর শেষ ইন্ডেক্স সমান হলে আমার
হাতে কিন্তু একটা উপাদান থাকবে , তখনও আমাকে খুজতে হবে তাই
কন্ডিশন (লেস অর ইকুয়াল ) দিলাম ।*/
{
int Mid_P = ( First_P + Last_P ) / 2; /* মিড পয়েন্ট বের করছি ......... */
if( ara[Mid_P] == x ) {/* সমান হয়ে গেলে তো x কে পেয়েই গেলাম, একবার পেয়ে গেলে
বোকার মত খুজা খুজির আর কি দরকার । তাই Pos_x এর মধ্যে
পজিশনটা রেখে লুপ ব্রেক করে দিব । */
Pos_x = Mid_P;
break;
}
else if( ara[Mid_P] > x ) Last_P = Mid_P - 1;
/* এখানে এসে যদি x এর মান মিড পয়েন্টের উপাদান থেকে
ছোট হয়ে যায় তবে মিড পয়েন্ট সহ আমারা পরের উপাদান গুলা
আমাদের সার্চ এরিয়ার বাইরে রাখব । এটা করার সবচে ভাল উপায়
হচ্ছে Last_P (শেষের পজিশন) কে Mid_P - 1 করে দেওয়া */
else First_P = Mid_P+1; /* উপরের একটা কন্ডিশনও যদি সত্য না হয় মানে , X যদি মিড
পয়েন্টের উপাদানের সমান না হয় আবার ছোটও না হয় তবে আমরা
সিওর x এর মান মিড পয়েন্টের উপাদানটি থেকে বড় । তাই তখন
আমরা মিড পয়েন্টের আগে উপাদান গুলো আমাদের সার্চ এরিয়া থেকে
বাদ দিয়ে দিব , এটা করার সবচে ভাল উপায় হচ্ছে
First_P (শেষের পজিশন) কে Mid_P + 1 করে দেওয়া . */
}
if( Pos_x == -1) printf("x not in array!\n");
else printf("x is in %dth index in this array.\n",Pos_x);
}
আশা করি কোডটা বুঝতে পেরেছো , কোডের ভিতর কমেন্টে যথেষ্ট ব্যাখ্যা করার চেষ্টা করেছি , তাও যদি না বুঝে থাক তবে আর্টিকেলটির নিচে তো কমেন্ট অপশন আছেই। কিছু জিজ্ঞেস করতে দ্বিধা করোনা ।
এখন তুমি x এর মান বদলে দেখতে পার কোড ঠিক ঠাক আছে কিনা ।
তোমার যদি ফাংশন সম্পর্কে হালকা পাতলা ধারনা থাকে তবে এই পুরো জিনিশটা ফাংশনের ভিতর লিখে ফেলতে পারো যেটি x এর পজিশন রিটার্ন করবে ।
এখন তোমার জন্য একটা প্রশ্ন।
——– array যদি ২৩২ (মানে হল প্রায় ৪ বিলিয়ন ) উপাদান থাকে, তবে বাইনারি সার্চ এলগোরিদমে সর্বোচ্চ কত বার তুলনা করবে কোন একটা সংখ্যা খুজে পাওয়া জন্য ?
তুমি নিজের মত চিন্তা কর, আমি জানি তুমি পারবে । উত্তর কত হবে, জানতে চাইলে কমেন্টে জানাতে পার।
আজ এ পর্যন্তই, পরবর্তী পর্বে থাকছে
–——- বাইনারি সার্চের recursive ইমপ্লিমেন্টেশন ও array -তে কোন নির্দিষ্ট উপাদান কত বার আছে তা বের করা।
সেই পর্যন্ত সবাই ভাল থাকো!
Mesbah Tanvir
Latest posts by Mesbah Tanvir (see all)
- বাইনারি সার্চঃ ১ম পর্ব - March 24, 2015
অনেক সুন্দর হয়েছে ভাইয়া 🙂
আপনাদের প্রোগ্রামিং পোস্ট গুলোর ধারাবাহিক সূচিপত্র থাকা উচিত ভাইয়া