binary_search.cpp

/*
Binary Search Patterns
Mathematical Foundation: Divide search space [l,r] by half
Invariant: answer ∈ [l,r], converge to single element
Three templates: find exact, find first true, find last true
Time: O(log n), Space: O(1)
*/

#include <bits/stdc++.h>
using namespace std;

// Template 1: Find Exact Target
// LeetCode: 704. Binary Search
// https://leetcode.com/problems/binary-search/
// Related:
// 374. Guess Number Higher or Lower
// https://leetcode.com/problems/guess-number-higher-or-lower/
// 278. First Bad Version
// https://leetcode.com/problems/first-bad-version/
// 702. Search in a Sorted Array of Unknown Size
// https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/
int binarySearch(vector<int>& a, int t) {
    int l = 0, r = a.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] == t) return m;
        a[m] < t ? l = m + 1 : r = m - 1;
    }
    return -1;
}

// Template 2: Find First Position where condition is true
// LeetCode: 34. Find First and Last Position of Element in Sorted Array
// https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
// Related:
// 35. Search Insert Position
// https://leetcode.com/problems/search-insert-position/
// 278. First Bad Version
// https://leetcode.com/problems/first-bad-version/
// 1095. Find in Mountain Array
// https://leetcode.com/problems/find-in-mountain-array/
// 1283. Find the Smallest Divisor Given a Threshold
// https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/
int findFirst(vector<int>& a, int t) {
    int l = 0, r = a.size();
    while (l < r) {
        int m = l + (r - l) / 2;
        a[m] >= t ? r = m : l = m + 1;
    }
    return l;
}

// Template 3: Find Last Position where condition is true
// LeetCode: 34. Find First and Last Position of Element in Sorted Array
// https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
// Related:
// 69. Sqrt(x)
// https://leetcode.com/problems/sqrtx/
// 1011. Capacity To Ship Packages Within D Days
// https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
// 1482. Minimum Number of Days to Make m Bouquets
// https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/
// 875. Koko Eating Bananas
// https://leetcode.com/problems/koko-eating-bananas/
int findLast(vector<int>& a, int t) {
    int l = -1, r = a.size() - 1;
    while (l < r) {
        int m = l + (r - l + 1) / 2;
        a[m] <= t ? l = m : r = m - 1;
    }
    return l;
}

// Search in Rotated Sorted Array
// LeetCode: 33. Search in Rotated Sorted Array
// https://leetcode.com/problems/search-in-rotated-sorted-array/
// Related:
// 81. Search in Rotated Sorted Array II
// https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
// 153. Find Minimum in Rotated Sorted Array
// https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
// 154. Find Minimum in Rotated Sorted Array II
// https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
// 1095. Find in Mountain Array
// https://leetcode.com/problems/find-in-mountain-array/
int search(vector<int>& a, int t) {
    int l = 0, r = a.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] == t) return m;
        if (a[l] <= a[m]) {
            (a[l] <= t && t < a[m]) ? r = m - 1 : l = m + 1;
        } else {
            (a[m] < t && t <= a[r]) ? l = m + 1 : r = m - 1;
        }
    }
    return -1;
}

// Find Minimum in Rotated Sorted Array
// LeetCode: 153. Find Minimum in Rotated Sorted Array
// https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
// Related:
// 154. Find Minimum in Rotated Sorted Array II
// https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
// 33. Search in Rotated Sorted Array
// https://leetcode.com/problems/search-in-rotated-sorted-array/
// 162. Find Peak Element
// https://leetcode.com/problems/find-peak-element/
// 852. Peak Index in a Mountain Array
// https://leetcode.com/problems/peak-index-in-a-mountain-array/
int findMin(vector<int>& a) {
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int m = l + (r - l) / 2;
        a[m] > a[r] ? l = m + 1 : r = m;
    }
    return a[l];
}

// Search 2D Matrix
// LeetCode: 74. Search a 2D Matrix
// https://leetcode.com/problems/search-a-2d-matrix/
// Related:
// 240. Search a 2D Matrix II
// https://leetcode.com/problems/search-a-2d-matrix-ii/
// 378. Kth Smallest Element in a Sorted Matrix
// https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
// 1351. Count Negative Numbers in a Sorted Matrix
// https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/
// 1337. The K Weakest Rows in a Matrix
// https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/
bool searchMatrix(vector<vector<int>>& a, int t) {
    int m = a.size(), n = a[0].size();
    int l = 0, r = m * n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        int val = a[mid / n][mid % n];
        if (val == t) return true;
        val < t ? l = mid + 1 : r = mid - 1;
    }
    return false;
}

// Find Peak Element
// LeetCode: 162. Find Peak Element
// https://leetcode.com/problems/find-peak-element/
// Related:
// 852. Peak Index in a Mountain Array
// https://leetcode.com/problems/peak-index-in-a-mountain-array/
// 1095. Find in Mountain Array
// https://leetcode.com/problems/find-in-mountain-array/
// 1901. Find a Peak Element II
// https://leetcode.com/problems/find-a-peak-element-ii/
// 1802. Maximum Value at a Given Index in a Bounded Array
// https://leetcode.com/problems/maximum-value-at-a-given-index-in-a-bounded-array/
int findPeakElement(vector<int>& a) {
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int m = l + (r - l) / 2;
        a[m] > a[m + 1] ? r = m : l = m + 1;
    }
    return l;
}

// Sqrt(x) - Binary Search on Answer
// LeetCode: 69. Sqrt(x)
// https://leetcode.com/problems/sqrtx/
// Related:
// 367. Valid Perfect Square
// https://leetcode.com/problems/valid-perfect-square/
// 50. Pow(x, n)
// https://leetcode.com/problems/powx-n/
// 875. Koko Eating Bananas
// https://leetcode.com/problems/koko-eating-bananas/
// 1011. Capacity To Ship Packages Within D Days
// https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
// 1482. Minimum Number of Days to Make m Bouquets
// https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/
// 1283. Find the Smallest Divisor Given a Threshold
// https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/
int mySqrt(int x) {
    int l = 0, r = x;
    while (l <= r) {
        long long m = l + (r - l) / 2;
        long long sq = m * m;
        if (sq == x) return m;
        sq < x ? l = m + 1 : r = m - 1;
    }
    return r;
}