> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/topics/binary-search.md).

# 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/>

```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/>

```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](/leetcode/topics/binary-search.md)
* [240-Search a 2D Matrix II](/leetcode/topics/binary-search.md)
* <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/>

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