အခန်း ၉ - Binary Search

Binary Search (တစ်ဝက်စီ ခွဲခြမ်းရှာဖွေခြင်း) ဆိုတာ Sorted (စီထားပြီးသား) ဖြစ်နေတဲ့ linear data structure (ဥပမာ - Array) တစ်ခုထဲကနေ ကိုယ်လိုချင်တဲ့ တန်ဖိုး (Target) ကို အလွန် လျင်မြန်စွာ ရှာဖွေနိုင်တဲ့ နည်းလမ်း တစ်ခု ဖြစ်ပါတယ်။

ပုစ္ဆာတွေမှာ အချိန်ကြာမြင့်မှု (Time Complexity) ကို O(log⁡n)O(\log n) အထိ လျှော့ချချင်တဲ့အခါ Binary Search ကို မဖြစ်မနေ သုံးကြရပါတယ်။

Binary Search ၏ အဓိက အယူအဆ

Binary Search ရဲ့ အလုပ်လုပ်ပုံကို နားလည်ဖို့ စီထားပြီးသား Array တစ်ခုထဲမှာ target ရှာတာ ကို တိုက်ရိုက်ကြည့်ရအောင်။

ဥပမာ nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] ဖြစ်ပြီး target = 23 ကို ရှာမယ်ဆိုပါစို့။

Binary Search မှာ left နဲ့ right က လက်ရှိရှာနေတဲ့ နယ်ပယ်ကို သတ်မှတ်ပါတယ်။ mid က အဲ့ဒီနယ်ပယ်ရဲ့ အလယ်နေရာပါ။ nums[mid] ကို target နဲ့ နှိုင်းယှဉ်ပြီး target မရှိနိုင်တဲ့ တစ်ဝက်ကို တစ်ခါတည်း ဖယ်ထုတ်သွားပါတယ်။

အဆင့်လိုက် ကြည့်ပါ။

အဆင့် ရှာနေသည့်နယ်ပယ် mid တန်ဖိုး နှိုင်းယှဉ်ချက် ဆက်လုပ်မည့်အရာ
၁ [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] 16 16 < 23 23 က ပိုကြီးလို့ ဘယ်ဘက်တစ်ဝက် [2, 5, 8, 12, 16] ကို ဖယ်
၂ [23, 38, 56, 72, 91] 56 56 > 23 23 က ပိုငယ်လို့ ညာဘက်တစ်ဝက် [56, 72, 91] ကို ဖယ်
၃ [23, 38] 23 23 == 23 တွေ့ပြီ၊ index 5 ကို return ပြန်

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

ပထမအဆင့်မှာ 16 ကို စစ်ပါတယ်။ target = 23 က 16 ထက် ပိုကြီးတဲ့အတွက် 16 အပါအဝင် ဘယ်ဘက်ခြမ်းမှာ target မရှိနိုင်တော့ပါဘူး။ ဒါကြောင့် ဘယ်ဘက်တစ်ဝက်ကို တစ်ခါတည်း ဖယ်ပါတယ်။

ဒုတိယအဆင့်မှာ 56 ကို စစ်ပါတယ်။ target = 23 က 56 ထက် ပိုငယ်တဲ့အတွက် 56 အပါအဝင် ညာဘက်ခြမ်းမှာ target မရှိနိုင်တော့ပါဘူး။ ဒါကြောင့် ညာဘက်တစ်ဝက်ကို ထပ်ဖယ်ပါတယ်။

နောက်ဆုံး ကျန်တဲ့နယ်ပယ် [23, 38] ထဲမှာ 23 ကို စစ်လိုက်တဲ့အခါ target ကို တွေ့သွားပါတယ်။

အခြေခံဆုံး စည်းမျဉ်းကို ဒီလို မှတ်နိုင်ပါတယ်။

အခြေအနေ ဘာလုပ်မလဲ
nums[mid] == target အဖြေတွေ့ပြီ၊ mid ကို return ပြန်
nums[mid] < target target က ညာဘက်မှာပဲ ရှိနိုင်လို့ left = mid + 1
nums[mid] > target target က ဘယ်ဘက်မှာပဲ ရှိနိုင်လို့ right = mid - 1

O(log⁡n)O(\log n) ၏ အစွမ်းထက်ပုံ

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

Binary Search တွင် သိထားရမည့် အခြေခံစည်းမျဉ်းများ

Binary Search ကို မှန်ကန်စွာ ရေးသားနိုင်ဖို့ အဓိက အချက် ၄ ချက်ကို နားလည်ထားရပါမယ်။

၁။ Pointers သုံးခု သတ်မှတ်ခြင်း

ရှာဖွေရမည့် ဘောင်ကို သတ်မှတ်ရန် left (အစ) နှင့် right (အဆုံး) pointer နှစ်ခု လိုအပ်ပြီး၊ နှိုင်းယှဉ်ရန် mid (အလယ်) pointer တစ်ခု လိုအပ်ပါသည်။

၂။ Integer Overflow ကို ရှောင်လွှဲခြင်း (Critical Tip)

အလယ်ကိန်း mid ကို ရှာတဲ့အခါ ပုံမှန်အားဖြင့် အောက်ပါအတိုင်း တွက်လေ့ရှိကြပါတယ် —

int mid = (left + right) / 2;

ဒီနည်းလမ်းက သာမန်အချိန်မှာ အလုပ်လုပ်ပေမယ့် left ရော right ပါ အလွန်ကြီးမားတဲ့ ကိန်းဂဏန်းတွေ ဖြစ်နေရင် (ဥပမာ - 2302^{30} ဝန်းကျင်)၊ နှစ်ခုပေါင်းလိုက်တဲ့အခါ int ရဲ့ အမြင့်ဆုံး သတ်မှတ်ချက်ထက် ကျော်လွန်ပြီး Integer Overflow ဖြစ်သွားစေနိုင်ပါတယ်။ ဒါကြောင့် mid ကို ရှာသည့် အခါမှာ အောက်ပါအတိုင်း ရေးသားကြပါတယ်။

int mid = left + (right - left) / 2;

၃။ Pointer များကို ရွေ့လျားပုံ (Boundary Update)

mid မှာ ရှိတဲ့ တန်ဖိုးနဲ့ target ကို နှိုင်းယှဉ်ပြီး ဘောင်တွေကို ကျဉ်းသွားစေရပါမယ်။

၄။ Infinite Loop မဖြစ်စေရန် (Common Pitfall)

Binary Search ရေးတဲ့အခါ အများဆုံး မှားတတ်တာက loop က ဘယ်တော့မှ မရပ်ဘဲ infinite loop ဖြစ်သွားတာ ပါ။ မှတ်ထားရမယ့် အချက် ၂ ချက် —

Lower Bound နှင့် Upper Bound

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

ဥပမာ nums = [1, 2, 2, 2, 5], target = 2 ဆိုရင် —

target ရှာတဲ့ template နဲ့ မတူတာက — တွေ့တာနဲ့ ချက်ချင်း မရပ်ဘဲ၊ ဖြစ်နိုင်ချေ အဖြေကို မှတ်ထားပြီး ဆက် သွားတာပါ။

// Lower bound: nums[i] >= target ဖြစ်တဲ့ ပထမဆုံး index
int lowerBound(int[] nums, int target) {
    int left = 0, right = nums.length; // right က length (out of range) က စသည်
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;   // mid က သေးနေသေးလို့ ညာဘက်
        } else {
            right = mid;      // mid ကိုယ်တိုင် အဖြေ ဖြစ်နိုင်လို့ ဖယ်မပစ်
        }
    }
    return left;
}

Upper bound အတွက်ဆို nums[mid] < target ကို nums[mid] <= target လို့ ပြောင်းရုံပါပဲ။ ဒီ pattern နှစ်ခုက အောက်က Search Insert Position နဲ့ First and Last Position ပုစ္ဆာတွေရဲ့ အခြေခံပါ။

Real-world မှာ ဘယ်လိုသုံးလဲ

Binary Search က "sorted ဖြစ်နေတဲ့ အရာ" ဒါမှမဟုတ် "monotonic (တစ်လမ်းသွား တိုး/လျော့) ဖြစ်တဲ့ အဖြေနယ်ပယ်" ရှိတိုင်း သုံးနိုင်ပါတယ်။

Questions

Binary Search ကို ကောင်းစွာ အသုံးချတတ်စေဖို့ အမေးအများဆုံး မေးခွန်းပုံစံတွေကို လွယ်ရာက ခက်ရာ တစ်ဆင့်ချင်း လေ့လာကြည့်ရအောင်။

၁။ Binary Search (Basic Template)

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log⁡n)O(\log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

ရှင်းလင်းချက်

ဒါကတော့ Binary Search ရဲ့ အခြေခံအကျဆုံး Template ပုစ္ဆာ ဖြစ်ပါတယ်။ ပေးထားတဲ့ Array က အငယ်ကနေ အကြီး အစဉ်လိုက် စီပြီးသား ဖြစ်တဲ့အတွက် left နဲ့ right pointer တွေကို သုံးပြီး target ကို ရှာဖွေသွားရမှာ ဖြစ်ပါတယ်။ left <= right ဖြစ်နေသရွေ့ ပတ်ပါမယ်။

Time Complexity: O(log⁡n)O(\log n) - အဆင့်တိုင်းမှာ search space က ထက်ဝက် လျော့သွားလို့ ဖြစ်ပါတယ်။
Space Complexity: O(1)O(1) - memory ပို ထပ်မယူလို့ ဖြစ်ပါတယ်။

Java Solution

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            // Integer Overflow မဖြစ်စေရန် တွက်နည်း
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid; // အဖြေရှာတွေ့ပါက index ကို ပြန်သည်
            } else if (nums[mid] < target) {
                // target က ပိုကြီးနေလျှင် ညာဘက်ခြမ်းတွင် ဆက်ရှာရန်
                left = mid + 1;
            } else {
                // target က ပိုငယ်နေလျှင် ဘယ်ဘက်ခြမ်းတွင် ဆက်ရှာရန်
                right = mid - 1;
            }
        }

        return -1; // ရှာမတွေ့ပါက -1 ပြန်သည်
    }
}

၂။ Search Insert Position

Sorted array nums (distinct values) နဲ့ target ပေးထားတယ်။ target ရှိရင် သူ့ index ကို ပြန်ပါ။ မရှိရင် target ကို စီထားတဲ့ အစဉ်အတိုင်း ထည့်သင့်တဲ့ index ကို ပြန်ပါ။

Example:

Input: nums = [1,3,5,6], target = 5   →  Output: 2
Input: nums = [1,3,5,6], target = 2   →  Output: 1
Input: nums = [1,3,5,6], target = 7   →  Output: 4

ရှင်းလင်းချက်

ဒါက အပေါ်က Lower Bound ကို တိုက်ရိုက် အသုံးချတာပါ။ nums[i] >= target ဖြစ်တဲ့ ပထမဆုံး index ဟာ — target ရှိရင် သူ့နေရာ၊ မရှိရင် ထည့်သင့်တဲ့နေရာ — အတိအကျ ဖြစ်နေပါတယ်။

Time Complexity: O(log⁡n)O(\log n) Space Complexity: O(1)O(1)

Java Solution

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length; // out-of-range index ကစသည် (ထည့်စရာ နေရာ ဖြစ်နိုင်လို့)

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid; // mid ကိုယ်တိုင် အဖြေ ဖြစ်နိုင်လို့ ဖယ်မပစ်
            }
        }

        return left;
    }
}

၃။ Find First and Last Position of Element

Sorted array nums ထဲမှာ target ရဲ့ ပထမဆုံး (first) နဲ့ နောက်ဆုံး (last) index ကို ရှာပါ။ မရှိရင် [-1, -1]။ O(log⁡n)O(\log n) ဖြစ်ရမယ်။

Example:

Input: nums = [5,7,7,8,8,10], target = 8   →  Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6   →  Output: [-1,-1]

ရှင်းလင်းချက်

target ထပ်နေနိုင်တဲ့အတွက် binary search ၂ ခါ လုပ်ပါမယ် —

Time Complexity: O(log⁡n)O(\log n) Space Complexity: O(1)O(1)

Java Solution

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = lowerBound(nums, target);
        // target မရှိလျှင်
        if (first == nums.length || nums[first] != target) {
            return new int[] { -1, -1 };
        }
        int last = lowerBound(nums, target + 1) - 1; // target+1 ၏ lower bound ၏ ရှေ့
        return new int[] { first, last };
    }

    // nums[i] >= key ဖြစ်တဲ့ ပထမဆုံး index
    private int lowerBound(int[] nums, int key) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

၄။ Search a 2D Matrix

You are given an m×nm \times n integer matrix matrix with the following two properties:

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log⁡(m×n))O(\log(m \times n)) time complexity.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

ရှင်းလင်းချက်

ဒီပုစ္ဆာမှာ Matrix (2D Array) တစ်ခု ပေးထားပေမယ့် ထူးခြားချက်က Row တစ်ခုချင်းစီဟာ စီထားပြီးသား ဖြစ်ရုံသာမက၊ နောက် Row ရဲ့ ပထမဆုံးဂဏန်းက အရှေ့ Row ရဲ့ နောက်ဆုံးဂဏန်းထက် အမြဲ ပိုကြီးနေပါတယ်။ ဒါဟာ တကယ်တော့ 2D Matrix သာ ဖြစ်နေပေမယ့် ဂဏန်းအားလုံးကို တန်းစီချလိုက်ရင် 1D Sorted Array တစ်ခုတည်း အတိုင်းပါပဲ။

ဒါကြောင့် 2D Matrix ကို 1D Array တစ်ခုလို စိတ်ကူးပုံဖော်ပြီး Binary Search သုံးနိုင်ပါတယ်။

Time Complexity: O(log⁡(m×n))O(\log(m \times n)) - 2D matrix တစ်ခုလုံးကို 1D array လို တစ်ကြိမ်တည်းနဲ့ ရှာဖွေနိုင်သောကြောင့် ဖြစ်သည်။
Space Complexity: O(1)O(1)

Java Solution

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;

        // 1D Array သဘောမျိုး အစ နှင့် အဆုံး သတ်မှတ်သည်
        int left = 0;
        int right = (rows * cols) - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Virtual 1D index 'mid' မှ 2D Row, Col သို့ ပြောင်းလဲခြင်း
            int midVal = matrix[mid / cols][mid % cols];

            if (midVal == target) {
                return true;
            } else if (midVal < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}

၅။ Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ithi^{th} pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

ရှင်းလင်းချက်

ဒီပုစ္ဆာက "Binary Search on Answer / Solution Space" လို့ ခေါ်တဲ့ အဆင့်မြင့် ပုံစံတစ်မျိုး ဖြစ်ပါတယ်။ ကျွန်တော်တို့က Array ထဲမှာ တန်ဖိုးတစ်ခုကို လိုက်ရှာတာ မဟုတ်ပါဘူး။ Koko ငှက်ပျောသီး စားရမယ့် အနည်းဆုံးနှုန်း k (တစ်နာရီ စားမယ့် အရေအတွက်) ကို စဉ်းစားရမှာ ဖြစ်ပါတယ်။

တစ်ပုံချင်းစီ စားတဲ့အခါ ကြာမယ့်အချိန်ကို Math.ceil((double)pile / k) သို့မဟုတ် Integer arithmetic သုံးပြီး (pile + k - 1) / k ဖြင့် ရှာနိုင်ပါတယ်။

Time Complexity: O(nlog⁡(max⁡(piles)))O(n \log(\max(piles))) - binary search ဘောင် [1, max(piles)] ကို O(log⁡(max⁡(piles)))O(\log(\max(piles))) အကြိမ် ပတ်ပြီး၊ အဆင့်တိုင်းမှာ O(n)O(n) အချိန်ယူ၍ piles အားလုံး စားချိန်ကို တွက်သောကြောင့် ဖြစ်သည်။
Space Complexity: O(1)O(1)

Java Solution

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;

        // အများဆုံး စားနှုန်းကို ရှာရန် Piles ထဲမှ အကြီးဆုံးတန်ဖိုးကို ရှာသည်
        for (int pile : piles) {
            right = Math.max(right, pile);
        }

        int result = right; // အဆိုးဆုံးနှုန်းဖြင့် စတင်ထားမည်

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // တစ်နာရီ 'mid' နှုန်းဖြင့် စားပါက စုစုပေါင်း ကြာမည့်နာရီ
            long totalHours = 0;
            for (int pile : piles) {
                // (pile + mid - 1) / mid သည် Math.ceil((double)pile / mid) နှင့် အတူတူပင်ဖြစ်သည်
                totalHours += (pile + mid - 1) / mid;
            }

            if (totalHours <= h) {
                // သတ်မှတ်ချိန်မီပါက ပိုနှေးသော စားနှုန်းကို ဆက်ရှာရန်
                result = mid;
                right = mid - 1;
            } else {
                // သတ်မှတ်ချိန်မမီပါက ပိုမြန်မြန် စားရန်
                left = mid + 1;
            }
        }

        return result;
    }
}

၆။ Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log⁡n)O(\log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

ရှင်းလင်းချက်

Sorted ဖြစ်နေတဲ့ Array တစ်ခုကို တစ်နေရာရာကနေ ဖြတ်ပြီး ခေါက်လိုက်တဲ့အခါ (Rotated sorted array)၊ Array ရဲ့ ပုံစံဟာ အပိုင်းနှစ်ပိုင်း ကွဲသွားပါတယ်။
အဓိက အယူအဆကတော့ — အပိုင်းတစ်ခုခုသည် အမြဲတမ်း စနစ်တကျ စီထားလျက် ရှိနေမည် ဖြစ်ပြီး၊ အခြားအပိုင်းတွင်မူ လှည့်ခေါက်ထားသော Pivot Point (အနည်းဆုံးတန်ဖိုး) ရှိနေပါလိမ့်မယ်။

ဤနေရာတွင် left < right ဟု သုံးရပါမည်။ ဘာကြောင့်လဲဆိုတော့ right = mid ဟု ပြောင်းလဲချိန်တွင် mid သည် အဖြေဖြစ်နိုင်သောကြောင့် loop မပတ်မိစေရန် ဖြစ်သည်။

Time Complexity: O(log⁡n)O(\log n)
Space Complexity: O(1)O(1)

Java Solution

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // အလယ်ကိန်းသည် ညာဘက်အစွန်းကိန်းထက် ကြီးနေလျှင် Pivot သည် ညာဘက်တွင်ရှိသည်
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                // အလယ်ကိန်းသည် ညာဘက်အစွန်းထက် ငယ်/ညီ နေပါက Pivot သည် ဘယ်ဘက်တွင် (သို့) mid ကိုယ်တိုင်ဖြစ်သည်
                right = mid;
            }
        }

        // left နှင့် right ဆုံသည့် နေရာသည် အနည်းဆုံးတန်ဖိုးဖြစ်သည်
        return nums[left];
    }
}

၇။ Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log⁡n)O(\log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

ရှင်းလင်းချက်

ဒီပုစ္ဆာက "Find Minimum in Rotated Sorted Array" အပေါ် ထပ်ဆင့်ပြီး target ကို ရှာခိုင်းတာ ဖြစ်ပါတယ်။ တစ်ဝက်ခွဲလိုက်တဲ့အခါ ဘယ်ဘက်ခြမ်း သို့မဟုတ် ညာဘက်ခြမ်း တစ်ဖက်ဖက်ဟာ အမြဲတမ်း ပုံမှန် Sorted ဖြစ်နေဆဲ ဆိုတဲ့ အချက်ကို အခြေခံပြီး ဖြေရှင်းရပါမယ်။

၁။ အရင်ဆုံး ဘယ်ဘက်ခြမ်း [left, mid] က ပုံမှန် Sorted ဖြစ်နေသလား သိဖို့ nums[left] <= nums[mid] ကို စစ်ဆေးပါတယ်။

၂။ အကယ်၍ ဘယ်ဘက်ခြမ်းက Sorted မဟုတ်ပါက၊ ညာဘက်ခြမ်း (mid, right] က မလွဲမသွေ ပုံမှန် Sorted ဖြစ်နေပါလိမ့်မယ်။

Time Complexity: O(log⁡n)O(\log n)
Space Complexity: O(1)O(1)

Java Solution

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            // ဘယ်ဘက်ခြမ်းသည် ပုံမှန် Sorted ဖြစ်နေသလား စစ်ဆေးသည်
            if (nums[left] <= nums[mid]) {
                // target သည် ဘယ်ဘက်ခြမ်း၏ ဘောင်ထဲတွင် ရှိနေသလား
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1; // ဘယ်ဘက်သို့ ရွေ့သည်
                } else {
                    left = mid + 1;  // ညာဘက်သို့ ရွေ့သည်
                }
            }
            // မဟုတ်ပါက ညာဘက်ခြမ်းသည် ပုံမှန် Sorted ဖြစ်နေရမည်
            else {
                // target သည် ညာဘက်ခြမ်း၏ ဘောင်ထဲတွင် ရှိနေသလား
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;  // ညာဘက်သို့ ရွေ့သည်
                } else {
                    right = mid - 1; // ဘယ်ဘက်သို့ ရွေ့သည်
                }
            }
        }

        return -1;
    }
}

၈။ Time Based Key-Value Store

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

Example 1:

Input:
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output:
[null, null, "bar", "bar", null, "bar2", "bar2"]

ရှင်းလင်းချက်

ဒီပုစ္ဆာကတော့ Database တွေမှာ Version ထိန်းချုပ်မှု (Timestamp tracking) အတွက် သုံးတဲ့ ပုံစံမျိုး ဖြစ်ပါတယ်။

Time Complexity:

  • set : O(1)O(1)
  • get : O(log⁡n)O(\log n) (ပေးထားသော Key အတွက် list အရွယ်အစား nn ပေါ်မူတည်၍)

Space Complexity: O(total_entries)O(total\_entries) - entries အားလုံးကို map ထဲတွင် သိမ်းဆည်းသောကြောင့် ဖြစ်သည်။

Java Solution

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class TimeMap {
    // Value နှင့် Timestamp ကို တွဲသိမ်းရန် Class တည်ဆောက်သည်
    private static class Node {
        String value;
        int timestamp;

        Node(String value, int timestamp) {
            this.value = value;
            this.timestamp = timestamp;
        }
    }

    private Map<String, List<Node>> map;

    public TimeMap() {
        map = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        map.putIfAbsent(key, new ArrayList<>());
        map.get(key).add(new Node(value, timestamp));
    }

    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) {
            return "";
        }

        List<Node> list = map.get(key);
        int left = 0;
        int right = list.size() - 1;
        String result = "";

        // Floor value ရှာရန် Binary Search
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (list.get(mid).timestamp <= timestamp) {
                // လက်ရှိ timestamp ထက် ငယ်/ညီပါက ဖြစ်နိုင်ချေရှိသောအဖြေအဖြစ် မှတ်ပြီး
                // ပိုကြီးသည့်အဖြေရှိနိုင်သေးသဖြင့် ညာဘက်သို့ ဆက်ရှာသည်
                result = list.get(mid).value;
                left = mid + 1;
            } else {
                // timestamp ကြီးနေပါက ဘယ်ဘက်သို့ ရွေ့သည်
                right = mid - 1;
            }
        }

        return result;
    }
}

၉။ Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log⁡(m+n))O(\log(m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

ရှင်းလင်းချက်

ဒါကတော့ Binary Search အခန်းရဲ့ အခက်ခဲဆုံးနဲ့ အဆင့်အမြင့်ဆုံး Hard အဆင့်ရှိ မေးခွန်း ဖြစ်ပါတယ်။ ပုံမှန်အားဖြင့် Arrays နှစ်ခုကို ပေါင်းပြီး Sort လုပ်ရင် O(m+n)O(m+n) ကြာပေမယ့်၊ ဒီပုစ္ဆာက O(log⁡(m+n))O(\log(m+n)) သာ ကြာအောင် စွမ်းဆောင်ရမှာ ဖြစ်ပါတယ်။

ဒါကို ဖြေရှင်းဖို့အတွက် "Partition (ပိုင်းခြားခြင်း) နည်းလမ်း" ကို သုံးရပါမယ်။
ကျွန်တော်တို့ လိုချင်တဲ့ အလယ်တန်ဖိုး (Median) ဆိုတာ စုစုပေါင်း Array ၂ ခုကို ဘယ်ခြမ်း (Left Partition) နဲ့ ညာခြမ်း (Right Partition) လို့ ညီတူညီမျှ ခွဲလိုက်တဲ့အခါ -

Array A (nums1):  [ ... A[i-1] | A[i] ... ]
Array B (nums2):  [ ... B[j-1] | B[j] ... ]
                  <-- Left --> | <-- Right -->

ကျွန်တော်တို့က အရွယ်အစား ပိုငယ်တဲ့ Array (ဥပမာ A) ပေါ်မှာ Binary Search စလုပ်ပါမယ်။

Time Complexity: O(log⁡(min⁡(m,n)))O(\log(\min(m, n))) - ပိုမိုတိုတောင်းသော array ပေါ်တွင်သာ binary search ပြုလုပ်သောကြောင့် အလွန်လျင်မြန်သည်။
Space Complexity: O(1)O(1)

Java Solution

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // nums1 က အမြဲတမ်း အရွယ်အစား ပိုငယ်စေရန် ပြောင်းလဲသည် (Binary Search ပိုမြန်စေရန်)
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;

        int left = 0;
        int right = m;
        int halfLen = (m + n + 1) / 2;

        while (left <= right) {
            int i = left + (right - left) / 2; // nums1 ၏ partition
            int j = halfLen - i;                // nums2 ၏ partition

            // နယ်နိမိတ်တန်ဖိုးများ သတ်မှတ်ခြင်း (Out of bounds ဖြစ်ပါက Infinity ယူသည်)
            int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];

            int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];

            // ခွဲခြားမှု မှန်ကန်မှု ရှိမရှိ စစ်ဆေးသည်
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                // စုစုပေါင်း အရေအတွက် မကိန်းဖြစ်လျှင်
                if ((m + n) % 2 != 0) {
                    return Math.max(maxLeft1, maxLeft2);
                }
                // စုစုပေါင်း အရေအတွက် စုံကိန်းဖြစ်လျှင်
                return ((long)Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
            }
            // nums1 ၏ ဘယ်ဘက်ခြမ်းသည် ကြီးလွန်းနေပါက ၎င်းအား လျှော့ရန်
            else if (maxLeft1 > minRight2) {
                right = i - 1;
            }
            // nums1 ၏ ဘယ်ဘက်ခြမ်းသည် ငယ်လွန်းနေပါက တိုးရန်
            else {
                left = i + 1;
            }
        }

        return 0.0;
    }
}