Binary Search,
discovered — not memorized

public int search(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {            // search space is [left, right], inclusive
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;  // found it
    else if (arr[mid] < target) left = mid + 1;  // target is in [mid+1, right]
    else right = mid - 1;           // target is in [left, mid-1]
    }
    return -1;                          // search space empty → not found
}

Invariant: "If target exists, it's at an index in [left, right]."
Why left <= right: The search space includes both endpoints. When left == right, there's still one element to check.
Why mid ± 1: We checked arr[mid] and it's NOT the target, so we exclude it.
Why return -1: The loop ended because left > right — the search space is empty, so target doesn't exist.

public int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length;    // right = n, NOT n-1: answer could be "past the end"
    while (left < right) {               // narrows to a single point
    int mid = left + (right - left) / 2;
    if (arr[mid] >= target) {
        right = mid;                  // mid could be the answer; keep it
    } else {
        left = mid + 1;              // mid is too small; exclude it
    }
    }
    return left;                          // left == right == first index where arr[i] >= target
}

Invariant: "The first index where arr[i] ≥ target is in [left, right]."
Why right = arr.length: If all elements are < target, the answer is "past the end" (index n). We need n in the search space.
Why right = mid (not mid-1): arr[mid] ≥ target means mid IS a valid candidate for "first ≥ target." We can't exclude it.
Why return left: Loop ends when left == right. The invariant collapses to "the answer IS left."

public int upperBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
    if (arr[mid] > target) {
        right = mid;
    } else {
        left = mid + 1;
    }
    }
    return left;
}

Only difference from lower bound: The predicate is arr[mid] > target instead of arr[mid] >= target. This finds the first element strictly greater than target. Used to compute the range of duplicates: [lowerBound, upperBound - 1].

public int[] searchRange(int[] arr, int target) {
    int first = lowerBound(arr, target);
    if (first == arr.length || arr[first] != target) return new int[]{-1, -1};
    int last = upperBound(arr, target) - 1;
    return new int[]{first, last};
}

Why this works: lowerBound gives the first index ≥ target. If that index has value ≠ target, target doesn't exist. Otherwise, upperBound - 1 gives the last index == target (since upperBound is the first index > target).

public int findMinimumFeasible(int lo, int hi) {
    int left = lo, right = hi;
    while (left < right) {
        int mid = left + (right - left) / 2;
    if (check(mid)) {
        right = mid;           // mid works; maybe something smaller also works
    } else {
        left = mid + 1;       // mid doesn't work; need something bigger
    }
    }
    return left;                    // the first (minimum) value where check is true
}

Invariant: "The minimum feasible value is in [left, right]."
Monotonicity: check(x) = false for x < answer, check(x) = true for x ≥ answer.
Why right = mid: If check(mid) is true, mid is feasible. The minimum feasible is ≤ mid. We keep mid in the search space.
Why left = mid + 1: If check(mid) is false, mid is NOT feasible. The minimum feasible is > mid. We exclude mid.

public int findMaximumFeasible(int lo, int hi) {
    int left = lo, right = hi;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;  // ROUND UP to avoid infinite loop
    if (check(mid)) {
        left = mid;            // mid works; maybe something bigger also works
    } else {
        right = mid - 1;      // mid doesn't work; need something smaller
    }
    }
    return left;                    // the last (maximum) value where check is true
}

Why mid = left + (right - left + 1) / 2 (round up): When check(mid) is true and we set left = mid, we need to guarantee that mid > left (otherwise left doesn't change → infinite loop). Rounding up ensures mid ≥ left + 1 when left < right. This is the critical difference from Template 5.

public int findMin(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
    if (arr[mid] > arr[right]) {
        left = mid + 1;         // min is in the right half (past the pivot)
    } else {
        right = mid;             // min is in the left half (mid could be the min)
    }
    }
    return arr[left];
}

The monotonic property: In a rotated sorted array like [4,5,6,1,2,3], compare arr[mid] with arr[right]. If arr[mid] > arr[right], the pivot (minimum) must be to the right of mid (because in a properly sorted portion, mid ≤ right). If arr[mid] ≤ arr[right], the pivot is at mid or to the left.

public int findPeakElement(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
    if (arr[mid] > arr[mid + 1]) {
        right = mid;             // descending here → peak is at mid or to the left
    } else {
        left = mid + 1;         // ascending here → peak is to the right
    }
    }
    return left;
}

The monotonic property: Compare arr[mid] with arr[mid+1]. If ascending (arr[mid] < arr[mid+1]), a peak must exist to the right (the array must eventually descend). If descending, a peak exists at mid or to the left. This works even without a sorted array — it exploits the slope.

A mountain array increases to a peak, then decreases. To search for a target: (1) find the peak using Template 8, (2) binary search the ascending left side, (3) if not found, binary search the descending right side (with reversed comparisons).

public int findInMountainArray(int[] arr, int target) {
    // Step 1: find the peak (Template 8)
    int peak = findPeak(arr);

    // Step 2: search the ascending left side [0, peak]
    int idx = ascBinarySearch(arr, 0, peak, target);
    if (idx != -1) return idx;

    // Step 3: search the descending right side [peak+1, n-1]
    return descBinarySearch(arr, peak + 1, arr.length - 1, target);
}

int ascBinarySearch(int[] arr, int lo, int hi, int target) {
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
    }
    return -1;
}

int descBinarySearch(int[] arr, int lo, int hi, int target) {
    while (lo <= hi) {              // same structure, REVERSED comparisons
int mid = lo + (hi - lo) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] > target) lo = mid + 1;  // reversed!
else hi = mid - 1;
    }
    return -1;
}

The array is sorted but you don't know its size (e.g., a stream or an ArrayReader interface). You can't set right = n-1 because you don't know n. Solution: exponentially grow a bound until you find an element ≥ target (or hit the end), then binary search within [bound/2, bound].

public int search(ArrayReader reader, int target) {
    // Step 1: find the search bound by doubling
    int hi = 1;
    while (reader.get(hi) < target) {
        hi *= 2;                // exponential growth: 1, 2, 4, 8, 16, …
    if (reader.get(hi) == Integer.MAX_VALUE) break; // past the end
    }
    int lo = hi / 2;           // we know target > reader.get(hi/2)

    // Step 2: standard binary search in [lo, hi]
    while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
int val = reader.get(mid);
if (val == target) return mid;
else if (val < target) lo = mid + 1;
else hi = mid - 1;
    }
    return -1;
}

Why exponential: Doubling the index finds a bound in O(log position) steps. Then binary search within the bound is also O(log position). Total: O(log position) — you never need to know n. This is called exponential search or galloping search.

Variant A — fully sorted matrix: Each row is sorted, and row[i][0] > row[i-1][last]. The entire matrix is a single sorted sequence if flattened. Map 1D index to 2D: row = idx / cols, col = idx % cols.

public boolean searchMatrix(int[][] mat, int target) {
    int rows = mat.length, cols = mat[0].length;
    int lo = 0, hi = rows * cols - 1;  // treat as 1D sorted array
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
    int val = mat[mid / cols][mid % cols];  // 1D → 2D mapping
    if (val == target) return true;
    else if (val < target) lo = mid + 1;
    else hi = mid - 1;
    }
    return false;
}

Variant B — row & column sorted (staircase search): Rows are sorted left→right, columns top→bottom, but rows don't chain. Start at the top-right corner. If current > target, move left. If current < target, move down. Each step eliminates a row or column.

public boolean searchMatrixII(int[][] mat, int target) {
    int row = 0, col = mat[0].length - 1;  // start at top-right
    while (row < mat.length && col >= 0) {
        if (mat[row][col] == target) return true;
        else if (mat[row][col] > target) col--;   // too big → go left
        else row++;                               // too small → go down
    }
    return false;
}

Why top-right: At the top-right corner, moving left gives smaller values and moving down gives larger values — it's a "decision point" like mid in 1D binary search. Starting at the bottom-left works too (reversed directions). Starting at top-left or bottom-right does not work — both directions give the same monotonicity, so you can't decide which way to go.

public double binarySearchReal(double lo, double hi) {
    double left = lo, right = hi;
    while (right - left > 1e-7) {       // precision threshold
        double mid = left + (right - left) / 2;
        if (check(mid)) {
            right = mid;                  // same logic as integer BS
        } else {
            left = mid;                   // NOTE: no +1 — reals have no gaps
        }
    }
    return left;                         // or (left + right) / 2
}

Key differences from integer BS: ① Loop condition is right - left > epsilon, not left < right — reals never "equal." ② left = mid (not mid + 1) because there are infinitely many reals between mid and mid+1 — you can't "skip" one. ③ Choose epsilon based on required precision. For competitive programming, 1e-7 or 1e-9 is standard. Alternatively, run a fixed number of iterations (e.g., 100) — after 100 halvings, the range has shrunk by 2¹⁰⁰, which is more than enough precision.

Example — Sqrt(x): Find √x to 5 decimal places. check(mid) = mid*mid > x. If true, sqrt is smaller → right = mid. If false, sqrt is larger → left = mid.

Representative problems: Koko Eating Bananas, Capacity To Ship Packages, Split Array Largest Sum, Minimize Maximum Distance to Gas Station, Magnetic Force Between Balls (maximize minimum variant).

The predicate pattern: "Given parameter = mid, simulate the process greedily. Does it satisfy the constraint?"

Representative problems: Aggressive Cows, Magnetic Force Between Balls, Allocate Minimum Number of Pages.

The predicate pattern: "Given minimum value = mid, greedily check if the constraint can be satisfied."

Key insight: In a rotated sorted array, one half of any split is always sorted. By comparing arr[mid] with arr[right], you determine which half contains the pivot.

Representative problems: Find Minimum in Rotated Sorted Array (I & II), Search in Rotated Sorted Array (I & II).

Key insight: You don't need a sorted array. The slope (ascending/descending) tells you which direction to go. A peak is guaranteed to exist because the boundaries are "virtual -∞."

Representative problems: Find Peak Element, Find Peak Element II (2D), Mountain Array (find the peak then search both sides).

Representative problems: Koko Eating Bananas, Ship Packages, Aggressive Cows, Allocate Pages, Painter's Partition.

Representative problems: Minimum Size Subarray Sum, Range Sum queries with optimization.

Representative problems: Search a 2D Matrix (I & II), Kth Smallest Element in a Sorted Matrix.

Representative problems: Sqrt(x), Find the Median of Two Sorted Arrays (partial), Minimize Max Distance to Gas Station (real-valued variant).

Key insight: You don't need to know n. Exponential growth finds a bound in O(log position) steps. The binary search within that bound is also O(log position). This is why it's called "exponential search" — the bound grows exponentially, but the total cost is logarithmic.

Representative problems: Search in Sorted Array of Unknown Size, Search in Infinite Sorted Array.

Key insight: The predicate is a graph traversal: "can I reach the destination using only edges with weight ≤ mid?" If yes, the minimum max-weight is ≤ mid. Monotonic: more edges allowed = easier to reach. This turns a graph problem into BS + BFS/DFS.

Representative problems: Path With Minimum Effort, Find the Safest Path in a Grid, Swim in Rising Water, Reachable Nodes in Subdivided Graph.

The predicate pattern: Build a subgraph with edges ≤ mid. Run BFS/DFS from source to destination. If reachable, check(mid) = true.

Key insight: Sometimes the feasibility check isn't a simple greedy — it's a DP. The outer binary search narrows the answer, and the inner DP verifies whether a given threshold is achievable. The total complexity is O(DP_time × log(range)).

Representative problems: Split Array Largest Sum (can also be greedy), Kth Smallest Subarray Sum, Capacity to Ship (when the greedy doesn't work and you need DP for the check), Median of Two Sorted Arrays (BS + partition logic that resembles DP).

The predicate pattern: check(mid) runs a DP that computes the minimum/maximum achievable cost. If that cost ≤ mid, return true. The DP exploits optimal substructure within the feasibility check.