Binary Search — Sorted Array ပေါ်က O(log n) ရှာဖွေမှု

နားလည်ထားရမယ့် အချက်

Linear search က element တစ်ခုချင်းစီကို check လုပ်တာမို့ worst case မှာ O(n) ဖြစ်တယ်။ Binary search ကတော့ sorted data ရဲ့ fact တစ်ခုကို အသုံးချပြီး ပိုကောင်းအောင် လုပ်တယ် — target ကို middle element နဲ့ compare လုပ်လိုက်ရင် target က ဘယ် half မှာရှိမယ်ဆိုတာ သိသွားတယ်၊ ဒါကြောင့် ကျန် half ကို ဆေးလုံးမကြည့်ဘဲ လုံးလုံးစွန့်ပစ်လို့ရတယ်။ ကျန်ရှိတဲ့ half ပေါ်မှာ ဒီအတိုင်းပြန်လုပ်ပြီး quarter ဆက်လုပ်တာမျိုး — comparison တစ်ခုချင်းစီက candidate ကျန်တဲ့ half ကို ဖျက်ပစ်ပေးလို့ total comparison က O(log n) ဖြစ်လာတယ်။ Element သန်းတစ်သန်းအတွက် comparison ၂၀ လောက်ပဲ လိုအပ်တယ် — သန်းချီလိုအပ်တဲ့ linear search နဲ့ ယှဉ်ရင်။ Strict ဖြစ်ပြီး negotiate မလုပ်နိုင်တဲ့ requirement တစ်ခုက input ကို sort ပြီးသားဖြစ်ရမယ်ဆိုတာပါ — binary search ရဲ့ halving logic က target ဟာ midpoint ရဲ့ ဘယ်ဘက်/ညာဘက်မှာရှိမယ်ဆိုတာ သိအောင် လုံးလုံးမှီတည်နေတာမို့ unsorted data ပေါ်မှာ ဒီ inference က မှားနေတာပါ။ အန္တရာယ်ရှိတဲ့ အချက်က unsorted input ပေါ်မှာ crash မဖြစ်ဘဲ silently wrong index ဒါမှမဟုတ် false 'not found' ကို return ပြန်ပေးတာပါ — crash ထက် debug လုပ်ဖို့ ပိုခက်တယ်။ ဒါက binary search tree ရဲ့ core idea အတူတူပဲ ဖြစ်ပေမယ့် linked tree structure အစား flat sorted array ပေါ်မှာ apply လုပ်တာပါ — pointer မလို index arithmetic ပဲ လိုတယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform က topic တစ်ခုစီရဲ့ lesson list ကို difficulty order အလိုက် sort ထားတယ်။ Learner တစ်ယောက်ကို 'သူ့ current level နဲ့ ညီမျှ ဒါမှမဟုတ် ပိုမြင့်တဲ့ ပထမဆုံး lesson' ဆီ တိုက်ရိုက်ပို့ချင်ရင် platform က ဒီ sorted list ကို linear scan လုပ်မယ့်အစား binary search လုပ်နိုင်တယ် — topic အားလုံးက lesson ရာနဲ့ချီရှိရင် comparison လက်တစ်ဆုပ်စာနဲ့ အားလုံးကို scan လုပ်ရတာကြားက ကွာခြားချက်ပါ။ ဒါက list ကို lesson ထည့်တိုင်း/reorder လုပ်တိုင်း တမင် sort ထိန်းထားလို့ပဲ အလုပ်လုပ်တာဖြစ်ပြီး editor တစ်ယောက်က sort order မထိန်းဘဲ lesson အသစ်ထည့်လိုက်ရင် ဒီ list ပေါ်က binary search က error တစ်ခုမှမပြဘဲ silently wrong result ပြန်ပေးမှာပါ — ဒါကြောင့် sanity check ဒါမှမဟုတ် assertion နဲ့ ကာကွယ်ထားသင့်တဲ့ failure mode အတိအကျပါပဲ။

Binary search က comparison တစ်ခုချင်းစီအတွက် search space ကို ထက်ဝက်စီ လျှော့ပြီး O(log n) ရရှိတယ်။
Input ကို sort ပြီးသား ဖြစ်ရမယ် — မဟုတ်ရင် silently wrong result ပြန်ပေးနိုင်တယ်၊ crash မဖြစ်ဘူး။
Binary search tree ရဲ့ core idea အတူတူပဲ ဖြစ်ပေမယ့် flat sorted array ပေါ်မှာ apply လုပ်ခြင်းပါ။

အတူတူ စမ်းရေးကြည့်မယ်

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  # not found

sorted_lessons = [3, 7, 12, 19, 25, 31, 40]
print(binary_search(sorted_lessons, 25))
print(binary_search(sorted_lessons, 5))

You should see

ပထမဆုံးအကြိမ်မှာ target 25 ရဲ့ index 4 ကို print ထုတ်ပြီး၊ ဒုတိယအကြိမ်မှာ target 5 ရှာမတွေ့လို့ -1 ကို print ထုတ်မည်။

၅ မိနစ် စမ်းကြည့်

binary_search function ကို unsorted list [19, 3, 40, 7, 25] နဲ့ run လုပ်ကြည့်ပါ — result မှန်ကန်ပါသလား စစ်ဆေးကြည့်ပြီး ဘာကြောင့်ဖြစ်နိုင်သလဲ ရှင်းပြကြည့်ပါ။

သတိလေးတစ်ချက်

Unsorted data ပေါ်မှာ binary search ကို run လုပ်ပြီး result မှားနေတာကို မသတိထားမိတတ်တယ် — error မတက်ဘဲ silently wrong index ပြန်လာလို့ debug လုပ်ဖို့ခက်တယ်။

mid ကို `(low + high) // 2` အစား `(low + high) / 2` သုံးပြီး integer index အစား float ပြန်ရလာအောင် လုပ်မိတတ်တယ် (ဒါမှမဟုတ် language တခြားဟာနဲ့ overflow ဖြစ်တတ်တယ်)။

Wikipedia — Binary search algorithm — Data Structures & Algorithms