Binary Search

Binary search ဆိုတာ search algorithms တွေထဲက တခုဖြစ်ပြီး Linear Search ထက် များသောအားဖြင့် ပိုမြန်တယ်။ များသောအားဖြင့်လို့ ပြောရခြင်းအကြောင်းက တချို့ case တွေမှာ linear search က ပိုမြန်လေ့ရှိလို့ဖြစ်တယ်။ Linear search နဲ့ မတူတာက Binary search အတွက်ဆို ရှိတဲ့ value တွေက sorting လုပ်ပြီးသားဖြစ်နေဖို့လိုအပ်တယ်။ တကယ်လို့ sort မလုပ်ရသေးဘူးဆို အရင် sort လုပ်ပြီးမှ binary search နဲ့ ရှာလို့ရတယ်။

သူ့မှာ O(log n) complexity ရှိတယ်။ ဆိုလိုတာက ရှိတဲ့ values တွေအကုန်လုံးကို ရှာတဲ့ O(n) ထက် ပိုမြန်တယ်။ တစ်ခါရှာပြီးတိုင်း value ထက်ဝက်လောက် လျော့သွားတယ်။

ဒီ values တွေထဲမှာ 6 ကို ရှာချင်တယ် ဆိုပါစို့။

Bineary Search မှာ အလယ် value က ကိုယ်လိုချင်တဲ့ value လား၊​ လိုချင်တာထက် ကြီးသလား၊ ငယ်သလား စပြီးစစ်တယ်။ ဒီမှာဆို အလယ်က value က 4 ဖြစ်တယ်။ အခုရှာချင်တဲ့ value က 6 ဖြစ်ပြီး ရောက်နေတာက 4 မို့လို့ ကိုယ် ရှာနေတာထက် ငယ်တယ်။

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

အဲ့ဒါဆို အခု value ၃ခုပဲကျန်တော့မယ်။ ပထမ step မှာလုပ်သလိုပဲ အလယ်က value ကို ထပ်ရှာမယ်။

ဒီမှာ အလယ်ဂဏန်းက လိုချင်တာထက် ကြီးသလား ငယ်သလားစစ်လိုက်တော့ ကြီးလဲ​မကြီးသလို ငယ်လဲမငယ်တော့ဘူး။ အဲ့တော့ ကိုယ်လိုချင်တဲ့ value ဖြစ်တဲ့ 6 ကို ရောက်သွားပြီ။

Binary search မှာ တခါစစ်တိုင်း ရှိတဲ့ size ရဲ့ ထက်ဝက်လောက်လျော့သွားတာကို တွေ့နိုင်မယ်။ စစချင်း size က ၇ခုရှိရာကနေ တခါလဲစစ်ပြီးရော ၃ခုပဲ ထပ်စစ်ဖို့လိုတော့တယ်။ အဲ့လိုပဲ ၁၀၀၀ လောက်ရှိတယ်ဆိုလဲ တခါစစ်တိုင်း ထက်ဝက်စီလျော့သွားလေ့ရှိလို့ binary search လို့နာမည်ပေးထားတာဖြစ်တယ်။

Binary Search implementation ကို ကြည့်မယ်ဆို (၂)နည်းရှိတယ်။ Iterative approach နဲ့ Recursive approach ဆိုပြီး ခွဲကြည့်လို့ရတယ်။

/**
 * Binary Search Iterative Approach
 * @param arr Sorted Array
 * @param key The value required
 * @returns found index or -1
 */
function binarySearch(arr, key){
    let startIndex = 0;
    let endIndex = arr.length - 1;

    while (startIndex <= endIndex) {
        let middle = Math.floor((startIndex + endIndex) / 2);

        if (arr[middle] === key) {
            return middle;
        } else if (arr[middle] < key) {
            startIndex = middle + 1;
        } else {
            endIndex = middle - 1;
        }
    }
    return -1;
}

/**
 * Binary Search Recursive Approach
 * @param arr Sorted Array
 * @param key The value required
 * @returns found index or -1
 */
function binarySearch(arr, key) {
  let middle = Math.floor(arr.length / 2);

  if (arr[middle] > key) {
    return binarySearch(arr.slice(0, middle), key);
  } else if (arr[middle] < key) {
    return binarySearch(arr.slice(middle + 1, arr.length), key);
  } else if (middle) {
    return middle;
  } else {
    return -1;
  }
}