বাইনারি সার্চের প্রাক্টিক্যাল ইমপ্লিমেন্টেশনের লিমিটেশন।

আচ্ছা আজকে বাইনারি সার্চের একটা প্রাক্টিক্যাল ইমপ্লিমেন্টেসান এর সীমাবদ্ধতা দেখি। 

আসা করা যাই আমরা সবাই জানি বাইনারি সার্চ কি, কিভাবে কাজ করে । তো দেখি আমরা কি সমস্যার সম্মুখিন হতে পারি বাইনারি সার্চ প্রাক্টিক্যালি ইমপ্লিমেন্ট করতে গেলে। 

ধরো, তোমাকে 100 থেকে 18,446,744,073,709,551,615 এর মধ্যে একটা  x  সংখ্যা খুঁজে বেড় করতে কতোবার খুঁজা লাগবে বলা হল। তুমি কি করবে?  সুন্দর করে তুমি বাইনারি সার্চের কোড লিখবে। (নিচের মতো করে)

unsigned long long b=100, e=18446744073709551615, mid,c=0;

while(b<e){

    mid = (b+e)/2;

    c++;

    if(mid==x) return c;

    if(mid<x) b=mid+1;

    else e=mid-1; 

}

কিন্তু একটু ভাবোতো , তোমার কোড কি  কাজ করবে?

আমার মনে হয় করবে না, তোমাদের কি মনে হয়?  

আচ্ছা আসো এখন দেখি কেন কাজ করবে না উপরের কোড টা। 

আসলে তোমাকে 100 থেকে 18446744073709551615 (2^⁶⁴ - 1) এর মধ্যে  x খুঁজে বের করতে কতবার খুঁজা লাগবে তা বের করতে বলা হয়েছে যেখানে তুমি b=100 (কোন সমস্যা নাই) এবং  e=18446744073709551615 (2^⁶⁴ - 1) যা  আসলে ULLONG_MAX, মানে  unsigned long long  var   এই  var  ভ্যারিয়েবলে সবচেয়ে বড় যেই সংখ্যাটি আটাতে পারবা সেটা  (2^⁶⁴ - 1)।  এর চেয়ে বড় কোন ভালু c/c++ এ  কোন ভারিয়েবলে নিলে তা overflow হবে। কোন কোন কম্পাইলার প্রোগ্রাম কে Runtime error এর সম্মুখিন করাবে।   

এখানে আমাদের কোডে আমরা কি করেছি একটু দেখি।

আমরা mid হিসাব করার জন্যে লিখেছি (b+e)/2; তাহলে এখানে তোমার কোড (উপরের মতো করে লিখলে) কি করবে? b+e আগে যোগ করবে, তারপর ২ দিয়ে ভাগ দিবে।  এখন তোমাকে খুঁজতে দেওয়া হয়েছে  x যেকোন  একটা ভ্যালু, তাহলে তোমার কোড অবশ্যই b=100, e=18446744073709551615  (2^⁶⁴ - 1) যোগ করবে, কিন্তু আসলেই কি b+e মানে ( 100+18446744073709551615) যোগ করতে পারবে ? আসলে পারবে না, overflow করবে। কারন (100+18446744073709551615) করলে অবশ্যই তা 18446744073709551615 (2^⁶⁴ - 1) এর থেকে বড় সংখ্যা হবে আর c/c++ এ 18446744073709551615  (2^⁶⁴ - 1) এর থেকে বড় সংখ্যা কোন ডাটা টাইপের ভ্যারিয়েবলে আটানো সম্ভাব না (String বাদ রাখি আপাতোত) তাই overflow হবে। যা একটু আগেই আমরা দেখে আসলাম কেন overflow করবে।.

তাহলে কি আমরা বাইনারি সার্চ দিয়ে এমন কিছু সার্চ করতে পারব না? নাকি বাইনারি সার্চ এমন পরিস্থিতিতে  কাজ করবে না? 

আসলে আমরা প্রাক্টিক্যালি  mid বের  করার জন্যে যেই equation টা  [mid = (b+e)/2 ;]  ব্যবহার করেছি তা ঠিক হয় নাই। থিওরিটিকালি এটা ঠিক হলেও প্রোগ্রামে লিখার সময় এমন লিমিটেশন  থাকলে আমরা  mid একটু অন্য ভাবে হিসেব করব।নিচের মতো করে।

    mid = b + (e-b)/2;

 

আচ্ছা এইবার দেখি উপরের ফাংশনটার মতো করে লিখলে আমাদের কি আর  overflow করবে? আসলে এইবার আর overflow করার কোন প্রশ্নই আসবে না। একটু খাতা কলমে নিজে চেস্টা করে দেখলেই পারো।

 

কারো কোন জিজ্ঞেসা/সংশোধনী  থাকলে কমেন্ট করে বলতে পার।