LC Patterns — Binary Search

int lo = 0, hi = n - 1;
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;                          // not found; loop ends with lo > hi

int lo = 0, hi = n;                 // hi = n so "no valid index" is representable
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (predicate(mid)) hi = mid;   // mid is Yes — keep it, it might be the boundary
    else lo = mid + 1;              // mid is No — boundary strictly to the right
}
return lo;                          // lo == hi == first Yes

while (lo < hi) {
    int mid = lo + (hi - lo + 1) / 2;   // RIGHT-biased — required when moving lo = mid
    if (predicate(mid)) lo = mid;       // searching for the LAST Yes
    else hi = mid - 1;
}
return lo;

What it is: The textbook case — a sorted array and one target, return its index (or where it would go). Compare the middle to the target, throw away the half that can't contain it, repeat until found or empty.

Intuition: the sorted order is the monotonic question ("is arr[i] ≥ target?"). Halve the space each step → O(log n).

int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

What it is: The array is sorted but the target appears many times (or you want its insertion edge) — find the first or last index satisfying a condition, not just any match. Keep narrowing until the search lands exactly on the edge of the matching block.

Intuition: with duplicates, "find target" becomes "find the edge of the target block." First occurrence = first index with arr[i] ≥ target (lower bound); last = upper_bound − 1. This is Template B in its purest form — and it's the foundation: every remaining pattern is a boundary search in disguise.

int lowerBound(vector<int>& a, int target) {   // first index with a[i] >= target
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= target) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
vector<int> searchRange(vector<int>& a, int target) {
    int first = lowerBound(a, target);
    if (first == (int)a.size() || a[first] != target) return {-1, -1};
    int last = lowerBound(a, target + 1) - 1;   // upper_bound - 1
    return {first, last};
}

What it is: A sorted array rotated at an unknown pivot (e.g. [4,5,6,7,0,1,2]) — no longer sorted overall, but still two sorted pieces stuck together. At each step work out which half around mid is properly sorted, then use that half's range to decide where the target could be.

Intuition: a rotated sorted array is two sorted runs. At any mid, at least one half is fully sorted — figure out which (compare arr[mid] with arr[lo]), check whether the target falls inside that sorted half's range, and go there. You're binary-searching on structure, not raw values.

int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) {                       // left half sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                          // right half sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

What it is: The array isn't sorted at all — it rises and falls like a mountain — and you must find a peak (bigger than both neighbors). You still halve the space because the direction of the slope at mid tells you which side a peak must be on.

Intuition: the slope at mid points to a peak. If arr[mid] < arr[mid+1], you're climbing → a peak lies to the right (the climb must turn or hit the end); otherwise a peak is at mid or left. The question "am I past the peak?" is monotonic on a mountain. Generalization: binary search works whenever a local comparison provably lets you throw away half.

int findPeakElement(vector<int>& nums) {
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < nums[mid + 1]) lo = mid + 1;  // climbing → peak on the right
        else hi = mid;                                // descending → peak here or left
    }
    return lo;
}

What it is: The problem asks for an optimal number — minimum speed, minimum capacity, fewest days, largest size — and there's no array to search at all. You guess a candidate answer, run a cheap "would this work?" check, and binary-search the smallest (or largest) guess that passes. The array is only used inside the checker.

Intuition: you're usually asked to minimize a maximum (or maximize a minimum): "min eating speed to finish in h hours," "min ship capacity for d days," "min largest subarray sum over k splits." Don't search the array — search the answer space. The check canDo(x) is monotonic: if speed x works, every speed above works too → FFFTTT → find the first Yes.

int minEatingSpeed(vector<int>& piles, int h) {
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
    auto hours = [&](int x) {
        long long t = 0;
        for (int p : piles) t += (p + x - 1) / x;   // ceil(p / x)
        return t;
    };
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (hours(mid) <= h) hi = mid;              // fast enough → try slower
        else lo = mid + 1;
    }
    return lo;
}

What it is: You need the k-th smallest element in a huge structured collection (a sorted matrix, all pairwise distances) too big to build and sort. Binary-search a candidate value and, using the structure, quickly count how many elements are ≤ it — the smallest value whose count reaches k is the answer.

Intuition: a sibling of Pattern 5 for k-th smallest in a structured space. The question count(x) = how many elements ≤ x only goes up as x grows → binary-search the smallest x with count(x) ≥ k. The structure (sorted rows) is what computes count(x) fast without enumerating.

int kthSmallest(vector<vector<int>>& m, int k) {
    int n = m.size(), lo = m[0][0], hi = m[n-1][n-1];
    auto countLE = [&](int x) {                 // O(n) staircase from bottom-left
        int cnt = 0, r = n - 1, c = 0;
        while (r >= 0 && c < n) {
            if (m[r][c] <= x) { cnt += r + 1; ++c; }
            else --r;
        }
        return cnt;
    };
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (countLE(mid) >= k) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

What it is: Same guess-and-check as Pattern 5, but the answer is a real number (a square root, a distance, an average), so there's no exact integer to land on. Halve the interval until it's smaller than the precision you need (or loop a fixed ~100 times) and return the midpoint.

Intuition: same monotonic-question idea, continuous answer. No integer to converge to — stop on precision (hi − lo > eps) or a fixed iteration count (~100 iterations covers any double — the cleaner choice). For integer problems like sqrt, prefer an integer Template C over floats.

int mySqrt(int x) {
    long long lo = 0, hi = x;
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;   // right-biased: last mid with mid² ≤ x
        if (mid * mid <= x) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}
// continuous version: for (int it = 0; it < 100; ++it) { double mid = (lo+hi)/2; ... }

What it is: The values you're searching over are never stored — they're computed from a formula on the index, like "how many numbers are missing before position i." You invent that formula, confirm it's monotonic, and binary-search it exactly as if it were a sorted array.

Intuition: the "array" is defined by a formula, not memory. The missing-count only grows → binary-search over it (1539). Index parity flips right after the single unpaired element (540). A pigeonhole count count(≤ mid) exposes the duplicate (287). You can binary-search any monotonic function of the index — the function stands in for arr[mid].

int findKthPositive(vector<int>& arr, int k) {
    int lo = 0, hi = arr.size();
    while (lo < hi) {                            // first index with missing(i) >= k
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] - (mid + 1) >= k) hi = mid;
        else lo = mid + 1;
    }
    return lo + k;                              // k + number of reals we skipped past
}

What it is: Two sorted arrays, and you need their combined median (or k-th element) without merging. Binary-search where to cut the first array; the size requirement forces the cut in the second, and comparing the four elements around the two cuts tells you whether to slide left or right.

Intuition: the median = the partition line cutting both arrays so the left halves together are half the total and every left element ≤ every right element. Binary-search the cut in the smaller array — the other cut is forced by the size rule. The question "is my cut too far right?" (A[i-1] > B[j]) is monotonic. O(log min(m, n)).

double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    if (A.size() > B.size()) swap(A, B);            // always search the smaller
    int m = A.size(), n = B.size(), half = (m + n + 1) / 2;
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = lo + (hi - lo) / 2, j = half - i;   // cut positions (0..m), not indices
        int Al = i ? A[i-1] : INT_MIN, Ar = i < m ? A[i] : INT_MAX;
        int Bl = j ? B[j-1] : INT_MIN, Br = j < n ? B[j] : INT_MAX;
        if (Al <= Br && Bl <= Ar) {
            if ((m + n) & 1) return max(Al, Bl);
            return (max(Al, Bl) + min(Ar, Br)) / 2.0;
        } else if (Al > Br) hi = i - 1;
        else lo = i + 1;
    }
    return 0.0;
}

What it is: Values written with timestamps or version numbers, and queries ask "what was the value at time t?" — where t may fall between writes. Each key's history is naturally sorted by time, so the query is a binary search for the rightmost entry with timestamp ≤ t.

Intuition: systems-flavored — values stored with timestamps; queries ask "the value at time ≤ t" → rightmost element ≤ t = classic (upper_bound − 1) over that key's list. This is Pattern 2 in a system-design costume (it's literally how LSM SSTables and snapshots do reads — nice to mention). Append-only ⇒ the list is sorted for free.

class TimeMap {
    unordered_map<string, vector<pair<int,string>>> m;   // key → (timestamp, value), increasing
public:
    void set(string key, string value, int timestamp) {
        m[key].push_back({timestamp, value});               // append-only ⇒ sorted for free
    }
    string get(string key, int timestamp) {
        auto& v = m[key];
        int lo = 0, hi = v.size();
        while (lo < hi) {                                    // first index with ts > timestamp
            int mid = lo + (hi - lo) / 2;
            if (v[mid].first <= timestamp) lo = mid + 1;
            else hi = mid;
        }
        return lo == 0 ? "" : v[lo - 1].second;             // step back to rightmost ts ≤ t
    }
};

What it is: Here binary search isn't the solution — it's the speed-up inside a bigger greedy or DP. You maintain a sorted helper array as you scan (the smallest tails of increasing subsequences, jobs by end time), and each element does one binary search into it, turning an O(n²) loop into O(n log n).

Intuition: binary search is the log-factor accelerator inside another algorithm. Patience sorting for LIS: keep tails[] (the smallest possible tail of an increasing subsequence of each length — provably sorted), each new element binary-searches where it belongs → O(n log n). Weighted job scheduling: a DP where each job binary-searches its latest non-overlapping predecessor.

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;                                 // tails[k] = smallest tail of an LIS of length k+1
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);    // x extends the longest run
        else *it = x;                                 // otherwise tighten a tail
    }
    return tails.size();
}