Minimal, copy-paste C++ for binary search, rotated arrays, 2D search, and answer-space search. Matches Data Structures lower/upper bound style.

Contents

Standard: [0, n-1], left <= right. Lower/upper bound: [0, n], left < right — same as Data Structures.

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

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

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

vector<int> searchRange(vector<int>& nums, int target) {
    int first = lower_bound(nums, target);
    if (first == (int)nums.size() || nums[first] != target) return {-1, -1};
    return {first, upper_bound(nums, target) - 1};
}
ID Title Link Solution
704 Binary Search Link -
34 Find First and Last Position Link -
35 Search Insert Position Link -
528 Random Pick with Weight Link Solution
300 Longest Increasing Subsequence Link Solution
673 Number of Longest Increasing Subsequence Link Solution

Binary search on rotated array

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

int findMin_rotated(const vector<int>& nums) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;
        else hi = mid;
    }
    return nums[lo];
}
ID Title Link Solution
33 Search in Rotated Sorted Array Link Solution
81 Search in Rotated Sorted Array II Link -
153 Find Minimum in Rotated Sorted Array Link -
154 Find Minimum in Rotated Sorted Array II Link -

Binary search on answer

Min valid: lo < hi, hi = mid when valid. Max valid: lo < hi, mid = lo + (hi - lo + 1) / 2, lo = mid when valid.

int minValid(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (valid(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int maxValid(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (valid(mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

// Example: Koko Eating Bananas (875)
int minEatingSpeed(vector<int>& piles, int h) {
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int hours = 0;
        for (int p : piles) hours += (p + mid - 1) / mid;
        if (hours <= h) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
ID Title Link Solution
875 Koko Eating Bananas Link -
1011 Capacity To Ship Packages Link -
410 Split Array Largest Sum Link -

Search in 2D matrix

Row/col sorted (240): start top-right, move left or down. Fully sorted row-major (74): flatten to 1D and binary search.

bool search2D_rc(const vector<vector<int>>& mat, int target) {
    int m = mat.size(), n = mat[0].size();
    int r = 0, c = n - 1;
    while (r < m && c >= 0) {
        if (mat[r][c] == target) return true;
        if (mat[r][c] > target) c--;
        else r++;
    }
    return false;
}

bool search2D_flat(const vector<vector<int>>& mat, int target) {
    int m = mat.size(), n = mat[0].size();
    int lo = 0, hi = m * n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int v = mat[mid / n][mid % n];
        if (v == target) return true;
        if (v < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}
ID Title Link Solution
74 Search a 2D Matrix Link -
240 Search a 2D Matrix II Link Solution
270 Closest Binary Search Tree Value Link Solution

Advanced

Merge sort on prefix sums (327, 315): Build prefix array, divide-and-conquer merge sort; for each right-half index j count left-half indices i with prefix[j]-upper <= prefix[i] <= prefix[j]-lower using two pointers. O(n log n).

Divide-and-conquer with counting: Recurse left/right, count cross pairs (e.g. inversions, reverse pairs), merge. See 493 Reverse Pairs, 315 Count Smaller.

Ternary search (unimodal): Split range in thirds; for max, move toward the higher side. Integer: when range ≤ 3, scan. E.g. 1515 Best Position for a Service Centre.

Exponential search (702): Double index until past target, then binary search in [i/2, min(i,n-1)].

Tree-based: Segment tree / Fenwick: Data Structures, Trees (tree walk, lazy segment, BIT).

ID Title Link
327 Count of Range Sum Link
315 Count of Smaller Numbers After Self Link
493 Reverse Pairs Link
702 Search in a Sorted Array of Unknown Size Link

More templates