This page collects ready-to-use C++ templates for every major binary search pattern you’ll encounter on LeetCode — from basic sorted-array lookup to rotated arrays, 2D matrices, and “search on the answer” optimization problems. Each section includes the template, a quick “when to use” guide, and a curated problem list so you can drill the pattern immediately. Templates match the Data Structures lower/upper bound style.

New to Binary Search? Binary search cuts the search space in half at each step, giving O(log n) time. The key: you need a monotonic condition — some property that’s false on one side and true on the other.

Binary Search: find 15 in [2, 5, 8, 11, 15, 18, 22] Step 1 258 1115 1822 lomidhi 11 < 15 → right Step 2 258 1115 1822 lomidhi 18 > 15 → left Step 3 258 1115 1822 found! 15 = target ✓ lo mid hi found

Contents

When to use: You see “find target in sorted array”, “first/last occurrence”, “search insert position”, or need the boundary of a condition in a sorted sequence.

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

Binary Search: find 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] Step 1 2 5 8 12 16 23 38 56 72 91 lo mid hi 16 < 23 → right Step 2 2 5 8 12 16 23 38 56 72 91 lo mid hi 56 > 23 → left Step 3 2 5 8 12 16 23 38 56 72 91 found! 23 = target ✓ lo mid hi found eliminated 
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

When to use: Problem says “rotated sorted array”, or you need to find a target or minimum in an array that was sorted then rotated.

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

When to use: You see “minimize maximum”, “maximum minimum”, “minimum capacity/speed”, or any optimization where you can check feasibility for a given answer value.

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

Binary Search on Answer — Find the Feasibility Boundary answer NOT FEASIBLE FEASIBLE 0 N Binary search narrows the range: valid(mid) = false → lo = mid + 1 (discard left half) valid(mid) = true → hi = mid (keep mid, search left half) lo and hi converge to the smallest feasible answer 
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

When to use: Problem says “search in matrix” or “sorted matrix”. Use staircase for row/col sorted matrices, flatten-to-1D for fully sorted row-major layouts.

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

When to use: Standard binary search won’t cut it — you need divide-and-conquer counting (inversions, range sums), ternary search on unimodal functions, or exponential search on unbounded arrays.

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

Quick Reference

Pattern Signal Phrases Key Insight
Basic “find target in sorted array” Standard lo/hi convergence
Lower/Upper Bound “first/last occurrence” lo < hi with half-open range
Rotated Array “rotated sorted array” One half is always sorted
Search on Answer “minimize maximum”, “capacity” Binary search on the answer value
2D Matrix “search in matrix” Treat as 1D or staircase search

More templates