# Binary search

## Binary Search

in a `**sorted array**`

* search index
* search value, [https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/](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/](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/)

```java
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;`

```java
// 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/](https://leetcode.com/problems/powx-n/description/)

```java
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](binary-search)
* [240-Search a 2D Matrix II](binary-search)
* [https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/)
* [https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/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-th-smallest-pair-distance/description/)
* [https://leetcode.com/problems/find-k-closest-elements/description/](https://leetcode.com/problems/find-k-closest-elements/description/)
* [https://leetcode.com/problems/k-th-smallest-prime-fraction/description/](https://leetcode.com/problems/k-th-smallest-prime-fraction/description/)
* [https://leetcode.com/problems/find-k-pairs-with-smallest-sums/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/minimize-max-distance-to-gas-station/description/) [https://leetcode.com/problems/k-th-smallest-prime-fraction](https://leetcode.com/problems/k-th-smallest-prime-fraction) [https://leetcode.com/problems/maximum-average-subarray-ii/description/](https://leetcode.com/problems/maximum-average-subarray-ii/description/)

```java
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
}
```
