একেবারেই সাধারন কথা বার্তা

এই পর্বে আমরা কম্পিউটার সাইন্সের অত্যন্ত জনপ্রিয় এবং মৌলিক একটি এলগোরিদম নিয়ে আলোচনা করবো, যার নাম বাইনারি সার্চ! কম্পিউটার সাইন্সের বিভিন্ন শাখায় বাইনারি সার্চের ব্যাপক ব্যবহার রয়েছে। ভূমিকা দিয়ে সময় নষ্ট না করে চল একটু শিখে ফেলার চেষ্টা করি বাইনারি সার্চের সবচাইতে সাদামাটা রূপটি!

এই এলগোরিদম শিখার জন্য যা যা জানা থাকতেই হবেঃ

  • array এর ব্যাসিক ধারনা থাকতে হবে।
  • loop  চালাতে পারতে হবে।

প্রথমে একটি ক্ষেত্রের এর কথা বলে নেই, যেটাতে আমরা বাইনারি সার্চ এপ্লাই করতে পারব। ধর তোমাকে integer -এর একটি sorted array দেওয়া আছে। /* সর্টেড না থাকলে সেটা সর্ট করে নিব। */  sorted array বলতে বোঝায়, array এর উপাদান গুলো increasing ( ছোট থেকে বড় হচ্ছে এমন ধারা) অথবা decreasing (বড় থেকে ছোট হচ্ছে এমন ধারা)  অর্ডারে আছে। আমরা আমাদের সমস্যায় array-এর উপাদান গুলো increasing  অর্ডারে আছে ধরে নিয়ে আলোচনা চালিয়ে যাবো। যেমন নিচের অ্যারেটিতে উপাদান গুলো sorted এবং তারা increasing  অর্ডারে আছে।

binary search 1st imge

দেখেই বোঝা যাচ্ছে এই array -তে ৯ টা উপাদান আছে। আর তুমি তো জানোই array -এর ইন্ডেক্স ০ থেকে শুরু হয় তাই এই array-এর শেষ ইন্ডেক্স হবে ৮। এখন তোমাকে একটা সংখ্যা দিয়ে বলবে সংখ্যাটি  array-টিতে আছে কিনা। যদি থাকে তবে কত নাম্বার ইন্ডেক্সে আছে। প্রবলেম দেখার পর প্রথমেই যে জিনিষটা মাথায় আসে, তা হল, সমস্ত array -টাতে লুপ চালিয়ে একটি একটি করে চেক করে দেখা উপাদান টা আছে নাকি নাই। কোডটা সি তে দেখতে এমন হবে ………

 /* কোড রান করতে সমস্যা হতে পারে, সেক্ষেত্রে বাংলাতে লেখা কমেন্ট গুলো ডিলিট করে দিও। */ 

উপরের কোডটা দেখে বুঝাই যাচ্ছে যে আমরা সর্টেড array  বৈশিষ্ট্য ব্যবহার করছি না । অর্থাৎ array টা যদি সর্টেড না থাকে তাহলেও এই কোড দিয়ে কাজ করা যাবে । এইভাবে কোন উপাদান খুজাকে বলে linear search

 

এখন কোন একটা এলগোরিদম লিখার আগে অবশ্যই এনালাইজ করতে হবে এর টাইম কমপ্লেক্সিটি কেমন হবে (এটা খুবই জরুরি)। লিনিয়ার সার্চ এর জন্য সবচেয়ে খারাপ কেসে [ উপাদানটি যদি array -তে না থাকে ] লুপ n সংখ্যক বার ঘুরবে, তাই লিনিয়ার সার্চ এর টাইম কমপ্লেক্সিটি হবে O(n) [এটা এভাবে পড়তে হয় – “Big O of n”] ।

এখন আমরা চেষ্টা করে দেখি এর টাইম কমপ্লেক্সিটি আরও কমানো যায় কিনা ।

তাহলে চল শুরু করা যাক।

 

বাইনারি সার্চের শুরু এখানেই

আগের উদাহন আরেকবার নেওয়া যাক।

binary search 1st imge

মনে করি এই array -তে x=47 সংখ্যাটি আছে কিনা খুজতে হবে , আর আমারা জানি array -টা সর্টেড । /* সর্টেড না থাকলে সেটা সর্ট করে নিব। */ 

প্রথমেই আমরা array-এর মিড পয়েন্ট বের করব। এখন array -এর মিড পয়েন্টে যে উপাদান আছে তার সাথে x এর তুলনা করব, যদি সমান হয়ে যায় তাহলে তো কেল্লা ফতে! আমরা পজিশন পেয়ে গেলাম। কিন্তু যদি সমান না হয়, তখন কি হবে?

সমান না হলে মিড পয়েন্টের উপাদানটি অবশ্যই x থেকে ছোট কিংবা বড় হবে [“হতেই হবে”  কারন এর বাইরে তো আর কিছু নেই]। উপরের array -তে মিড পয়েন্টের উপাদানটি 36 [ ইন্ডেক্স 4]।

1stmid

 

নিঃসন্দেহে 36,  x-এর চেয়ে ছোট। এখন যেহেতু বলা আছে array -টা সর্টেড তাহলে ইন্ডেক্স 0, 1, 2 , 3 এর উপাদান গুলো অবশ্যই 36 এর চাইতে ছোট হবে ( তা না হলে তো আর অ্যারেটা সর্টেড হল না )। তাই 36  এর আগে x এর মান থাকার কোন সম্ভাবনাই নেই, কিন্তু 36 এর পর অর্থাৎ ইন্ডেক্স 5 , 6 , 7 বা 8 এ থাকার সম্ভাবনা আছে [ সম্ভাবনা আছে বলছি কারন আমরা জানি না সংখ্যাটি array -তে আছে নাকি নাই ]। এখন যেই অংশে থাকার বিন্দু মাত্র সম্ভাবনা নেই, সেই অংশে x এর মান খুজতে যাওয়া বোকামি। আমরা প্রোগ্রামাররা যথেস্ট চালাক, তাই আমরা ওই অংশ বাদ দিয়ে চিন্তা করব। আর যেহেতু x, 36-এর সমান নয়, সেটাও চিন্তার বাইরে রাখব।

1stmidoff

এবার আমাদের কাছে 5 থেকে 8 ইন্ডেক্স পর্যন্ত উপাদান আছে যেখানে আমরা x কে খুজব। এখন আমরা আবার এই চারটি উপাদান এর মিড পয়েন্ট বের করব উপাদানটিকে দেখব x এর সমান কি না [এখন যেহেতু ইন্ডেক্স 5-8 পর্যন্ত্ জোড় সংখ্যক উপাদান বাকি তাই 6 বা 7 যেকোনো একটা কে মিড পয়েন্ট ধরলেই হবে, আমরা 6 কে মিড ধরে এগুতে থাকি।]

2nd mid

এখন মাঝখানের উপাদান 63, এটি x এর সমান না এবং x থেকে বড় । 63 এর ডান দিকে x থাকার কোন সম্ভাবনা নেই, তাই ৬৩ সহ পরের গুলা বাদ দিয়ে দেই।

2nd mid off

এখন বাকি আছে ইন্ডেক্স 5 এর উপাদান, যেহেতু একটা বাকি তাই সেটাকেই মিড পয়েন্ট ধরব ।

last

এখন এটাকে x এর সাথে তুলনা করি। দুইটা সমান, তাই আমরা আমাদের কাঙ্খিত পজিশন পেয়ে গেছি। বাইনারি সার্চের কাজ এখানেই শেষ ।

এখন উপরের ঘটনাকে কোডে ইমপ্লিমেন্ট করতে পারলেই আমাদের কাজ শেষ ।

চল এখন C তে এর কোডটা দেখি

 

আশা করি কোডটা বুঝতে পেরেছো , কোডের ভিতর কমেন্টে যথেষ্ট ব্যাখ্যা করার চেষ্টা করেছি , তাও যদি না বুঝে থাক তবে আর্টিকেলটির নিচে তো কমেন্ট অপশন আছেই। কিছু জিজ্ঞেস করতে দ্বিধা করোনা ।

এখন তুমি x এর মান বদলে দেখতে পার কোড ঠিক ঠাক আছে কিনা ।

তোমার যদি ফাংশন সম্পর্কে হালকা পাতলা ধারনা থাকে তবে এই পুরো জিনিশটা ফাংশনের ভিতর লিখে ফেলতে পারো যেটি x এর পজিশন রিটার্ন করবে ।

এখন তোমার জন্য একটা প্রশ্ন।

——–  array যদি ৩২ (মানে হল প্রায়  ৪  বিলিয়ন ) উপাদান থাকে, তবে বাইনারি সার্চ এলগোরিদমে সর্বোচ্চ কত বার তুলনা করবে কোন একটা সংখ্যা খুজে পাওয়া জন্য ?

তুমি নিজের মত চিন্তা কর, আমি জানি তুমি পারবে । উত্তর কত হবে, জানতে চাইলে কমেন্টে জানাতে পার।

আজ এ পর্যন্তই, পরবর্তী পর্বে থাকছে

–——- বাইনারি সার্চের recursive ইমপ্লিমেন্টেশন ও array -তে কোন নির্দিষ্ট উপাদান কত বার আছে তা বের করা।

সেই পর্যন্ত সবাই ভাল থাকো!

Mesbah Tanvir

Mesbah Tanvir

Mesbah Tanvir

Latest posts by Mesbah Tanvir (see all)