Binary Search ဆိုတာ ဘာလဲ? ရှာတာကို တစ်ဝက်စီ ဖြတ်တဲ့နည်း

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

ကျွန်တော် ဒါကို နားလည်သွားတာ အဘိဓာန်ဖွင့်တဲ့ အချိန်မှာ ဖြစ်တယ်။ “Zebra” ဆိုတဲ့ စကားလုံးကို အဘိဓာန်ထဲမှာ ရှာချင်တယ်ဆိုပါစို့။ စာမျက်နှာ ၁ ကနေ စပြီး တစ်ရွက်ချင်း လှန်မယ်ဆိုရင် စာမျက်နှာ ၁၀၀၀ လောက် လှန်ရမယ်။ ဒါပေမယ့် လူတိုင်းက အဲဒီလို မလုပ်ဘူး။ အလယ်လောက်က ဖွင့်ကြည့်တယ်။ “M” လောက်နဲ့ စတဲ့စာမျက်နှာ တွေ့ရင် Zebra က အနောက်ဘက်မှာ ရှိမယ်ဆိုတာ သိတယ်။ အဲဒီဘက်ခြမ်းရဲ့ အလယ်ကို ထပ်ဖွင့်တယ်။ အဲဒီလို တစ်ဝက်စီ ဖြတ်သွားရင် တစ်ခါလှန်တိုင်း ရှာရမယ့်နေရာက တစ်ဝက်လျော့သွားတယ်။ Binary Search က အဲဒီအတိုင်းပဲ။

ဘယ်လိုအလုပ်လုပ်တာလဲ?

စာရင်းတစ်ခုရှိတယ်ဆိုပါစို့ — [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]။ ဒီထဲမှာ 23 ကို ရှာချင်တယ်။

အရင်ဆုံး အလယ်က နံပါတ်ကို ကြည့်တယ်။ စာရင်းမှာ ၁၀ ခုရှိတော့ အလယ်က 16 (သို့မဟုတ် 23) ဖြစ်တယ်။ 16 က 23 ထက် သေးတယ်။
ဒါကြောင့် 23 က ညာဘက်ခြမ်းမှာ ရှိရမယ်ဆိုတာ သိတယ်။ ဘယ်ဘက်ခြမ်းတစ်ခုလုံးကို ဖယ်လိုက်လို့ရပြီ။ ကျန်တာ [23, 38, 56, 72, 91] ပဲ။
အဲဒီခြမ်းရဲ့ အလယ်က 56 ကို ကြည့်တယ်။ 56 က 23 ထက် ကြီးတယ်။ ဒါကြောင့် 23 က ဘယ်ဘက်မှာ ရှိရမယ်။ ကျန်တာ [23, 38] ပဲ။
အလယ်က 23 ကို ကြည့်တယ်။ တွေ့ပြီ။ စုစုပေါင်း ၃ ကြိမ်ပဲ စစ်လိုက်ရတယ်။

တစ်ခုချင်း လိုက်ရှာရင် ၅ ကြိမ် စစ်ရမှာကို Binary Search နဲ့ ၃ ကြိမ်နဲ့ ပြီးတယ်။ စာရင်းသေးရင် ကွာခြားမှု သိပ်မသိသာဘူး။ ဒါပေမယ့် စာရင်း ကြီးသွားရင် ကွာခြားမှုက ကြီးမားသွားတယ်။

ဘာလို့ ဒီလောက်မြန်တာလဲ?

စာရင်းမှာ အခု ၁ သန်းရှိတယ်ဆိုပါစို့။ တစ်ခုချင်း ရှာရင် အဆိုးဆုံးအခြေအနေမှာ ၁ သန်းကြိမ် စစ်ရမယ်။ Binary Search နဲ့ဆိုရင် တစ်ကြိမ်စစ်တိုင်း ရှာရမယ့်နေရာက တစ်ဝက်လျော့သွားတယ်။ ၁ သန်းကို တစ်ဝက်စီ ဖြတ်သွားရင် ၂၀ ကြိမ်လောက်နဲ့ ပြီးတယ်။ ၁ သန်းနဲ့ ၂၀ — ကွာခြားမှုက အဲဒီလောက်ကြီးတယ်။

ဒါကို Computer Science မှာ O(log n) လို့ ခေါ်တယ်။ n က စာရင်းအရွယ်အစား၊ log က တစ်ဝက်စီ ဖြတ်တဲ့အကြိမ်အရေအတွက်ပေါ့။ အရေအတွက် နှစ်ဆ တိုးသွားတိုင်းမှာ တစ်ကြိမ်ပဲ ပိုစစ်ရတယ်။ ဒါကြောင့် Database ကြီးတွေ၊ Search Engine တွေမှာ Binary Search က အခြေခံနည်းတစ်ခု ဖြစ်နေတာပါ။

တစ်ခုသတိထားရမှာက

Binary Search က စီထားပြီးသား စာရင်းမှာပဲ အလုပ်လုပ်တယ်။ အဘိဓာန်က A ကနေ Z အထိ စီထားလို့သာ အလယ်ဖွင့်တဲ့နည်း အလုပ်ဖြစ်တာပါ။ စာရင်းက ရှုပ်နေရင် အလယ်က နံပါတ်က ဘာကိုမှ ပြောပြနိုင်မှာ မဟုတ်ဘူး။ ဒါကြောင့် Binary Search သုံးမယ်ဆိုရင် အရင်ဆုံး စာရင်းကို စီရတယ် (Sorting)။ စီပြီးသား စာရင်းကို ခဏခဏ ရှာရမယ်ဆိုရင်တော့ Sorting လုပ်ရတဲ့ အချိန်က တန်တယ်။

ကိုယ်တိုင် စမ်းကြည့်ချင်ရင် Python မှာ ဒီလိုရေးလို့ရတယ်။


def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Code က တိုတိုလေးပဲ။ low နဲ့ high က ရှာနေတဲ့ ခြမ်းရဲ့ အစနဲ့ အဆုံးကို မှတ်ထားတယ်။ mid က အလယ်ပါ။ target နဲ့ mid ကို နှိုင်းပြီး ဘယ်ဘက်လား ညာဘက်လား ဆုံးဖြတ်တယ်။ မတွေ့ရင် -1 ပြန်ပေးတယ်။

ဒီလိုလုပ်လေ့ရှိတဲ့ အမှားတစ်ခု ရှိတယ် — mid တွက်တဲ့အခါ (low + high) // 2 ကို သုံးတာက ဂဏန်းအလွန်ကြီးတဲ့အခါ overflow ဖြစ်နိုင်တယ်။ တချို့ Language တွေမှာ low + (high – low) // 2 လို့ ရေးကြတယ်။ Python မှာတော့ ဒီပြဿနာ မရှိဘူး။

ဘယ်နေရာတွေမှာ သုံးတာလဲ?

Database တွေမှာ Index က Binary Search လို အလုပ်လုပ်တယ်။ စာရင်းကြီးထဲက Row တစ်ခုကို ချက်ချင်းရှာနိုင်တာက Index ကြောင့်ပါ။
Git မှာ git bisect ဆိုတဲ့ Command က Bug ဘယ် Commit က စဖြစ်တာလဲ ရှာဖို့ Binary Search သုံးတယ်။ Commit ၁၀၀၀ လုံးကို တစ်ခုချင်း စစ်မယ့်အစား တစ်ဝက်စီ ဖြတ်ပြီး ရှာတယ်။
Game တွေမှာ နံပါတ်ခန့်မှန်းတဲ့ Game — “၁ ကနေ ၁၀၀ ကြားက နံပါတ်တစ်ခုကို ခန့်မှန်းပါ၊ ကြီးတယ် သေးတယ်ပဲ ပြောမယ်” ဆိုတဲ့ Game မှာ အကောင်းဆုံးနည်းက အလယ်ကနေ စခန့်မှန်းတာပဲ။ အဲဒါ Binary Search ပဲ။

နောက်တစ်ခါ စာရင်းကြီးထဲမှာ တစ်ခုခု ရှာရင် တစ်ခုချင်း လိုက်ရှာမယ့်အစား အလယ်ကနေ စပြီး တစ်ဝက်စီ ဖြတ်ကြည့်ပါ။ ရှာတာ မြန်သွားတာ ကိုယ်တိုင် သတိထားမိလိမ့်မယ်။ 🙂