বাইনারি সার্চ

শুরু করতেছি একটা পাজোল দিয়ে , মনে কর, তোমাকে বললাম , একজন এক থেকে ১০০০ এর মধ্যে একটা সংখ্যা ধর, তোমাকে বের করতে হবে  answer yes বা no হয়, এরকম মিনিমাম কয়টা প্রশ্ন জিজ্ঞেস কওরে উত্তর টা বের করতে পারবে!

কিছুক্ষণ চিন্তা কর এটা নিয়ে , না পারলে পরের অংশে আসো।

এই জিনিস টা বাইনারী সার্চ দিইয়ে আমরা সহজে এবং দ্রুত বের করতে পারি।
মনে কর, এখানে আমাদের রেঞ্জ হল ১ থেকে ১০০০।  আমরা সবসময় রেঞ্জ এর মাঝখান এর সংখ্যা দিয়ে জিজ্ঞেস করব যে সংখ্যা টি সেটা থেকে বড় নাকি  ?
যেমন প্রথম এ জিজ্ঞেস করব সংখ্যাটি ৫০০ এর চেয়ে ব নাকি ?
যদি বড় হয়, তবে আমাদের রেঞ্জ কে ৫০০১ থেকে ১০০০ বানাবো, নয়ত ১ থেকে ৫০০।
তারপর আবার যে নতুন রেঞ্জ পাব, তাদের মাঝখানের সংখ্যা নিয়ে, এভাবে দেখা যাবে log(1000) এর মধ্যে বের কওরে ফেলা যাবে সংখ্যাটি।
সুতরাং বুঝতেই পারছ বাইনারী সার্চ কতটা ফাস্ট!!!

এখন মনে হওতে পারে, এটার কোড কেমন হবে? আমরা যেটা করব, একটা low রাখব, যেটা রেঞ্জ এর লোয়ার লিমিট হবে, আর একটা high থাকবে, যেটা রেঞ্জ এর আপার লিমিট হবে, আমরা কাজ করব , mid = ( low _ high)/ 2 নিয়ে , তারপর দরকার মত , low & high এর ভ্যালু চেঞ্জ করব, যখন low আর high সমান হয়ে যাবে, আমাদের কাজ ও শেষ :D

sample code:

while( low < high )
{
     mid = ( low + high)/ 2
    if( calc(mid) > value ) hi = mid
    else lo = mid+1
}

  আচ্ছা, যদি ফ্লোটিং নাম্বার হয়? তখন কিন্তু এভাবে করলে হবে না , তখন যেটা করতে হয়, লুপ টা একটা নির্দিস্ট সঙ্খ্যক বার ঘুরাতে হওয়, মোটামুটি ৬০ থেকে ১০০ বার এর মত ঘুরানোই এনাফ, আর আমরা যেমন lo = mid+1 করেছি, ওটা না করে lo = mid করব।

count = 0

while( count < 100 )
{
     count++
     mid = ( low + high)/ 2
    if( calc(mid) > value ) hi = mid
    else lo = mid
}

এখন বাইনারি সার্চ আমরা সেখানেই এপ্লাই করব যেখানে ফাংশন টা বলা থাকবএ non-increasing or non-decreasing , যদি এমন হয় যে কিছু পরিমাণ non-increasing  , আবার কিছু পরিমাণ non-decreasing তাহলে কিন্তু বাইনারি সার্চ দিয়ে হবে না, তখন "টারনারি সার্চ " নামে আরেকটা জিনিস লাগে, যেটা পরবর্তী কোন পর্বে থাকবে !

আর পরবর্তী পর্বে আমরা বাইনারি সার্চ নিয়ে আরও কিছু প্রবলেম লভ দেখব, stay tuned :p