Binary search

Binary Search

in a **sorted array**

• search index

• search value, https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

Two types:

• shrink, have upper and lower bound

• expand, as a multiplication

Shrinkage Template

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/

class Solution {
    public int findMin(int[] nums) {
        // Corner case
        if (nums.length == 0) return -1;
        if (nums.length == 1) return nums[0];
        if (nums[0] < nums[nums.length -1]) return nums[0];

        // Narrow the range
        // Key: 1) left + 1 < right 2) right = mid;left = mid;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid-1]) return nums[mid];
            if (nums[mid] > nums[0]) {
                left = mid;
            } else if (nums[mid] < nums[0]) {
                right = mid;
            } else {
                if (nums[mid] <= nums[left]){
                    left++;
                } else {
                    right--;
                }
            }
        }

        // Determine left and right   
        if (nums[left] < nums[right]) {
            return nums[left];
        } else {
            return nums[right];
        }
    }
}

Option 1: left <= right, left = mid + 1, right = mid - 1 Option 2: stop at left and right point, then compare 2 points. left + 1 < right, right = mid;left = mid;

// Always use this template
while (left + 1 < right) {
    int mid = left + (right - left) / 2;
    int missingNum = getMissingNum(nums, left, mid);
    if (missingNum >= k) {
        right = mid;
    } else {
        left = mid;
        k -= missingNum;
    }
}

Expand Template

https://leetcode.com/problems/powx-n/description/

public double myPow(double x, int n) {
    if (n < 0) {
        return 1 / powHelper(x, -n);
    }
    return powHelper(x, n);
}

public double powHelper(double x, int n) {
    if (n == 0) return 1;
    long exp = 1;
    double base = x;
    while (exp * 2 <= n) {
        base = base * base;
        exp = exp * 2;
    }
    return base * myPow(x, n - (int)exp);
}

Binary Serarch in Matrix

• 074-Search a 2D Matrix
• 240-Search a 2D Matrix II
• https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/
• https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/

similar idea:

• https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/
• https://leetcode.com/problems/find-k-closest-elements/description/
• https://leetcode.com/problems/k-th-smallest-prime-fraction/description/
• https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/

Double binary search

while (left + 1e-6 < right) https://leetcode.com/problems/minimize-max-distance-to-gas-station/description/ https://leetcode.com/problems/k-th-smallest-prime-fraction https://leetcode.com/problems/maximum-average-subarray-ii/description/

while (l + 1e-6 < r) {
    double mid = l + (r - l) / 2;
    int cnt = stationCnt(stations, mid);
    if (cnt > K) l = mid; 
    else r = mid; // we want the result smaller, so when cnt == K, set r = mid, try a smaller one
}