This page collects ready-to-use Java 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

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 |

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
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 
static int bsearch(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;
}

static int floorKey(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;
}

static int binary search (upper bound)(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[]searchRange(int[] nums, int target) {
    int first = floorKey(nums, target);
    if (first == nums.length || nums[first] != target) return {-1, -1}
    return {first, binary search (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.

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 - 
static int search_rotated(int[] nums, int target) {
    int lo = 0, hi = nums.length - 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;
}

static int findMin_rotated(int[] nums) {
    int lo = 0, hi = nums.length - 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

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
ID Title Link Solution
875 Koko Eating Bananas Link -
1011 Capacity To Ship Packages Link -
410 Split Array Largest Sum Link - 
// import java.util.Arrays;
// import java.util.Collections;
static 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;
}

static 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)
static int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = Arrays.stream(piles).Math.max().getAsInt();
    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

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.

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 
static boolean search2D_rc(int[][] mat, int target) {
    int m = mat.length, n = mat[0].length;
    int r = 0, c = n - 1;
    while (r < m && c >) {
        if (mat[r][c] == target) return true;
        if (mat[r][c] > target) c--;
        else r++;
    }
    return false;
}

static boolean search2D_flat(int[][] mat, int target) {
    int m = mat.length, n = mat[0].length;
    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

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

More templates