Binary Search ဆိုတာဘာလဲ

binary search ဆိုတာ search algorithm တမျိုးဖြစ်တယ်။ binary search problem တွေ မဖြေရှင်းခင်မှာ ကျွန်တော်တို့ binary search ဘာလဲ၊ ဘယ်လို အလုပ်လုပ်လဲ သိထားဖို့လိုပါတယ်။ input dataset ကသာ sort လုပ်ထားပြီးသား ဖြစ်မယ်ဆိုရင် ကိုယ်လိုချင်တဲ့ value ရဲ့ position ကို အထိရောက်ဆုံးနဲ့ အမြန်ဆုံး ရှာဖို့ binary search ကို သုံးတယ်။

binary search ရဲ့ အလုပ်လုပ်ပုံကတော့ dataset ကို နှစ်ပိုင်းပိုင်း၊ ကိုယ်ရှာနေတဲ့ value မရှိနိုင်တဲ့ တခြမ်းကို ပစ်လိုက်ပြီး ကျန်တခြမ်းကို ဒီလိုပဲ နှစ်ပိုင်း ဆက်ပိုင်းသွားရင်းက အဖြေကို ရှာတဲ့ပုံစံဖြစ်တယ်။ အဘိဓာန်ထဲမှာ စာလုံးရှာသလိုပါပဲ။ lion ဆိုတဲ့စာလုံးကို ရှာတယ် ထားပါတော့။ တရွက်ချင်း လှန်ပြီး l အထိသွားတာက ထိရောက်တဲ့ ရှာနည်း မဟုတ်ပါဘူး။ အဲဒီအစား ကျွန်တော်တို့ binary search သုံးပြီး ရှာမယ်ဆိုရင် ဒီလိုဖြစ်လိမ့်မယ်။

စာအုပ်ရဲ့တဝက်ကို လှန်လိုက်လို့ ပေါ်လာတဲ့စာလုံးက m ဆိုရင် l က m ရဲ့ ရှေ့မှာမို့လို့ လက်ရှိစာမျက်နှာကနေ နောက်တခြမ်းလုံးကို ဖယ်ပစ်လိုက်နိုင်တယ်။ ကျန်တဲ့ စာမျက်နှာတွေကို တဝက်တခါ ထပ်ဝက်လို့ ရလာတဲ့စာလုံးက g ဆိုရင် ရှေ့တခြမ်းလုံးကို ထပ်ဖယ်ပါတယ်။ ဘာလို့လဲဆိုတော့ g ပြီးမှ m လာတာမို့ပါ။ ဒီလိုနဲ့ နောက်ဆုံးမှာ l ကိုရောက်သွားမယ်။

စာအုပ်က ၂၀၄၈ မျက်နှာရှိရင် အများဆုံးမှ ၁၁ ကြိမ် ပဲရှာရပါမယ်။ ပထမတကြိမ်မှာ ရှာစရာ 1024 မျက်နှာ ကျန်မယ်။ 2nd turn မှာ 512 မျက်နှာကျန်မယ်။ ဒီလိုနဲ့ 11 ကြိမ်မြောက်မှာ 1 မျက်နှာပဲ ကျန်ပါမယ်။ ဒါကြောင့် binary search မှာ loop တကြိမ်ပတ်ပြီးတိုင်း ရှာရမယ့် input size ထက်ဝက် လျော့သွားပါတယ်။ ဒီအချက်ကြောင့်ပဲ input size အကြီးကြီးတွေကို binary search က ကောင်းကောင်း ကိုင်တွယ်နိုင်ပါတယ်။

complexity အရပြောရင် အကြိမ်တိုင်းမှာ input size ကို တဝက်စီ လျှော့ချသွားတဲ့အတွက် ဒါက logarithmic property တခုဖြစ်တယ်။ log 8 base 2 လို့ ရေးရင် 8 ကနေ 1 ရအောင် base ဖြစ်တဲ့ 2 နဲ့ ဘယ်နှခါ စားရမလဲလို့ မေးသလိုပါပဲ။ 2^3 = 8 ဖြစ်တဲ့အတွက် 3 ခါစားရပါမယ်။ log 8 base 2 = 3 ဖြစ်သလို element 8 လုံးပါတဲ့ array ကို ထက်ဝက် 3 ကြိမ်ဝက်ရင်လည်း နောက်ဆုံးတလုံးတည်း ကျန်မှာပါ။ အဲဒီလိုပဲ log 2048 base 2 က 11 ဖြစ်တဲ့အတွက် အဘိဓာန် ဥပမာမှာ နောက်ဆုံးတမျက်နှာတည်း ကျန်ဖို့ 11 ကြိမ် လှန်ခဲ့ရပါတယ်။

space complexity ဖက်ဆိုရင် binary search ရဲ့ iterative implementation အတွက် memory လိုအပ်ချက်က input size အပေါ်မှာ မမူတည်တဲ့အတွက် constant ပါ။ ဒါပေမယ့် recursive implementation မှာတော့ call stack ကြောင့် recursion depth ဖြစ်တဲ့ O(logN) ဖြစ်တယ်။ binary search ရဲ့ အားနည်းချက်လို့ ပြောမယ်ဆိုရင် input က sort ပြီးသားဖြစ်ဖို့ လိုတယ်ဆိုတာပါပဲ။

ဒါတွေကတော့ binary search ဘာလဲ၊ ဘယ်လိုအလုပ်လုပ်လဲဆိုတာပါပဲ။