> ## Content Index
> Fetch the complete content index at: https://arkar.dev/llms.txt
> Use this file to discover other available public pages before exploring further.

# Binary Search
- URL: https://arkar.dev/react-native-setup/
- Published: 2023-08-24T16:49:14.000Z
- Updated: 2024-06-26T09:59:12.000Z
- Author: Arkar Min Tun
- Tags: algorithms

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 ထက်ဝက်လောက် လျော့သွားတယ်။

![](https://arkar.dev/content/images/2024/06/image-10.png)

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

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

![](https://arkar.dev/content/images/2024/06/image-11.png)

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

![](https://arkar.dev/content/images/2024/06/image-12.png)

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

![](https://arkar.dev/content/images/2024/06/image-13.png)

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

![](https://arkar.dev/content/images/2024/06/image-14.png)

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

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

```javascript
/**
 * 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;
}
```

```javascript
/**
 * 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;
  }
}
```