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.

def bsearch(self, a, target):
    lo = 0, hi = (int)len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) / 2
        if (a[mid] == target) return mid
        if (a[mid] < target) lo = mid + 1
        else hi = mid - 1
    return -1
def lower_bound(self, a, target):
    lo = 0, hi = (int)len(a)
    while lo < hi:
        mid = lo + (hi - lo) / 2
        if (a[mid] < target) lo = mid + 1
        else hi = mid
    return lo
def upper_bound(self, a, target):
    lo = 0, hi = (int)len(a)
    while lo < hi:
        mid = lo + (hi - lo) / 2
        if (a[mid] <= target) lo = mid + 1
        else hi = mid
    return lo
def searchRange(self, nums, target):
    first = lower_bound(nums, target)
    if (first == (int)len(nums)  or  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

def search_rotated(self, nums, target):
    lo = 0, hi = (int)len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) / 2
        if (nums[mid] == target) return mid
        if nums[mid] >= nums[lo]:
            if (target >= nums[lo] * and  target < nums[mid]) hi = mid - 1
            else lo = mid + 1
             else :
            if (target > nums[mid] * and  target <= nums[hi]) lo = mid + 1
            else hi = mid - 1
    return -1
def findMin_rotated(self, nums):
    lo = 0, hi = (int)len(nums) - 1
    while lo < hi:
        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.

def minValid(self, lo, hi):
    while lo < hi:
        mid = lo + (hi - lo) / 2
        if (valid(mid)) hi = mid
        else lo = mid + 1
    return lo
def maxValid(self, lo, hi):
    while lo < hi:
        mid = lo + (hi - lo + 1) / 2
        if (valid(mid)) lo = mid
        else hi = mid - 1
    return lo
# Example: Koko Eating Bananas (875)
def minEatingSpeed(self, piles, h):
    lo = 1, hi = max_element(piles.begin(), piles.end())
    while lo < hi:
        mid = lo + (hi - lo) / 2
        hours = 0
        for (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.

def search2D_rc(self, mat, target):
    m = len(mat), n = mat[0].__len__()
    r = 0, c = n - 1
    while r < m  and  c >= 0:
        if (mat[r][c] == target) return True
        if (mat[r][c] > target) c -= 1
        else r += 1
    return False
def search2D_flat(self, mat, target):
    m = len(mat), n = mat[0].__len__()
    lo = 0, hi = m  n - 1
    while lo <= hi:
        mid = lo + (hi - lo) / 2
        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