Quick Reference O(log n) / O(1) 
int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 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;
}
Use when
  • Sorted or rotated sorted array
  • Find boundary/peak/minimum
  • Search space halvable each step
  • 'Find first/last position'
Watch out
  • Integer overflow with (lo+hi)/2
  • Infinite loop from wrong mid+/-1
  • Wrong comparison for first vs last occurrence
Pattern

Modified Binary Search

Apply binary search beyond simple sorted arrays — rotated arrays, search spaces, and answer-based searching.

Roadmap

  1. What Is This Pattern?
  2. When to Use It
  3. Variant 1 — Standard Binary Search
  4. Variant 2 — First/Last Occurrence
  5. Variant 3 — Rotated Sorted Array
  6. Variant 4 — Binary Search on Answer
  7. Template Code
  8. Common Problems
  9. Interactive Demo
  10. Complexity Analysis
  11. Key Takeaways
Step 01

What Is This Pattern?

Standard binary search finds a target in a sorted array in O(log n) time by repeatedly halving the search space. Modified binary search adapts this same halving technique to problems where the search space is not a simple sorted array — rotated arrays, partially sorted data, or even abstract numeric ranges where you search for the optimal answer.

The Core Idea

Maintain two pointers, lo and hi, that bound the search space. Compute mid, evaluate a condition, then discard half the space. Repeat until the answer is found.

Sorted array: searching for target = 7
1
3
5
7
9
12
15
lo
mid
hi
lo pointer
mid pointer
hi pointer
💡

The power of halving: Each iteration eliminates half the remaining candidates. For n = 1,000,000 elements, binary search needs at most 20 comparisons. Linear search would need up to 1,000,000.

Step 02

When to Use It

Look for these recognition signals in the problem statement. If you spot one or more, modified binary search is very likely the intended approach.

"Sorted or partially sorted array"
The data has some ordering property you can exploit to discard half the space.
"Find the minimum/maximum that satisfies..."
Optimization over a range where you can check feasibility for a given value.
"Monotonic predicate"
If condition holds for x, it holds for all x' > x (or vice versa). The answer is at the boundary.
"Search space can be halved"
You can evaluate a condition at mid and definitively rule out one half of the remaining range.
⚡

Not just arrays! Binary search works on any search space where you can evaluate a predicate at a midpoint and discard one half. This includes abstract numeric ranges (e.g., "what is the minimum speed?"), not just physical arrays.

Step 03

Variant 1 — Standard Binary Search

Classic

The classic template. Search for an exact target in a sorted array. Return its index, or -1 if not found. The loop uses lo <= hi because a single element (lo == hi) is still a valid candidate.

Template

int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // avoids overflow

        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;  // not found
}

Walkthrough: arr = [1, 3, 5, 7, 9, 12, 15], target = 9

Iter 1:
1
3
5
7
9
12
15
mid=3, 7 < 9, go right
Iter 2:
1
3
5
7
9
12
15
mid=5, 12 > 9, go left
Iter 3:
1
3
5
7
9
12
15
mid=4, found 9!

Found target 9 at index 4 in just 3 iterations out of 7 elements.

Step 04

Variant 2 — First/Last Occurrence

Lower/Upper Bound

When duplicates exist, the standard template returns any matching index. To find the leftmost or rightmost occurrence, we change the loop condition to lo < hi and avoid returning early when we find a match — instead, we continue searching to tighten the bound.

First Occurrence (Lower Bound)

// Returns index of first element >= target
int lo = 0, hi = arr.length - 1;

while (lo < hi) {
    int mid = lo + (hi - lo) / 2;

    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;  // don't skip mid — it might be the answer
}
// lo == hi == index of first occurrence (if it exists)

Last Occurrence (Upper Bound)

// Returns index of last element <= target
int lo = 0, hi = arr.length - 1;

while (lo < hi) {
    int mid = lo + (hi - lo + 1) / 2;  // round UP to avoid infinite loop

    if (arr[mid] > target) hi = mid - 1;
    else lo = mid;  // don't skip mid — it might be the answer
}
// lo == hi == index of last occurrence (if it exists)

Walkthrough: arr = [1, 3, 5, 5, 5, 8, 9], target = 5 (first occurrence)

Iter 1:
1
3
5
5
5
8
9
mid=3, 5 == 5, hi = mid
Iter 2:
1
3
5
5
5
8
9
mid=1, 3 < 5, lo = mid+1
Iter 3:
1
3
5
5
5
8
9
lo == hi == 2, done!

First occurrence of 5 is at index 2. The key: when arr[mid] == target, we set hi = mid (not return mid) to keep searching left.

🎯

Round-up trick for last occurrence: When lo = mid is possible, use mid = lo + (hi - lo + 1) / 2 (rounding up). Otherwise, when lo == mid and the else branch sets lo = mid, the loop never terminates.

Step 05

Variant 3 — Rotated Sorted Array

Rotated

A sorted array has been rotated at an unknown pivot. For example, [0,1,2,4,5,6,7] becomes [4,5,6,7,0,1,2]. The key insight: at least one half around mid is always sorted. Determine which half is sorted, then check if the target falls within that sorted half.

The Rotation "Break Point"

The array has two sorted segments separated by a break where the values drop.

4
5
6
7
0
1
2
sorted segment 1 break sorted segment 2

Algorithm

int searchRotated(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;

        if (arr[lo] <= arr[mid]) {
            // Left half [lo..mid] is sorted
            if (arr[lo] <= target && target < arr[mid])
                hi = mid - 1;  // target in sorted left half
            else
                lo = mid + 1;  // target in right half
        } else {
            // Right half [mid..hi] is sorted
            if (arr[mid] < target && target <= arr[hi])
                lo = mid + 1;  // target in sorted right half
            else
                hi = mid - 1;  // target in left half
        }
    }
    return -1;
}

Walkthrough: arr = [4, 5, 6, 7, 0, 1, 2], target = 0

Iter 1:
4
5
6
7
0
1
2
left sorted [4..7], 0 not in [4,7), go right
Iter 2:
4
5
6
7
0
1
2
right sorted [1..2], 0 not in (1,2], go left
Iter 3:
4
5
6
7
0
1
2
mid=4, found 0!

Found target 0 at index 4 in 3 iterations. At each step, we identified which half was sorted and checked if the target could be there.

💡

Why does arr[lo] <= arr[mid] work? In a rotated array, the rotation break falls in exactly one half. If arr[lo] <= arr[mid], the break is not in the left half, so the left half is properly sorted. Otherwise, the right half from mid to hi is sorted.

Step 06

Variant 4 — Binary Search on Answer

Search on Answer

Instead of searching through an array, search through the answer space. Define a range [lo, hi] of possible answers, then use a feasibility predicate to halve the range. This technique is extremely powerful for optimization problems.

Example: Capacity to Ship Packages in D Days (#1011)

Packages have weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Ship in 5 days. What is the minimum ship capacity?

lo = max(weights) = 10
The ship must carry at least the heaviest single package.
hi = sum(weights) = 55
At most, ship everything in one day.
feasible(capacity): can we ship in ≤ D days?
Greedily load packages in order. Count how many days it takes. If days ≤ D, the capacity is feasible.

Template

int shipWithinDays(int[] weights, int days) {
    int lo = 0, hi = 0;
    for (int w : weights) {
        lo = Math.max(lo, w);  // min capacity = heaviest package
        hi += w;                 // max capacity = total weight
    }

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(weights, mid, days))
            hi = mid;           // can do it — try smaller
        else
            lo = mid + 1;       // cannot do it — need bigger
    }
    return lo;
}

boolean feasible(int[] weights, int capacity, int days) {
    int dayCount = 1, currentLoad = 0;
    for (int w : weights) {
        if (currentLoad + w > capacity) {
            dayCount++;
            currentLoad = 0;
        }
        currentLoad += w;
    }
    return dayCount <= days;
}
🎯

The monotonic property: If capacity X works (feasible), then any capacity > X also works. If capacity X does not work, then no capacity < X works either. This monotonicity is what makes binary search valid here.

Step 07

Template Code

These four templates cover the vast majority of binary search problems. Memorize the differences in loop conditions and pointer updates.

1. Standard Binary Search

// Find exact target in sorted array. Returns index or -1.
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {                          // <= because single element is valid
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;     // found — return immediately
    else if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

2. First Occurrence (Lower Bound)

// Find leftmost position where arr[i] >= target
int lo = 0, hi = arr.length - 1;
while (lo < hi) {                           // < because lo == hi is the answer
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;                          // keep mid — it might be the first
}

3. Rotated Sorted Array

// Search for target in a rotated sorted array
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;

    if (arr[lo] <= arr[mid]) {              // left half is sorted
        if (arr[lo] <= target && target < arr[mid])
            hi = mid - 1;
        else lo = mid + 1;
    } else {                                // right half is sorted
        if (arr[mid] < target && target <= arr[hi])
            lo = mid + 1;
        else hi = mid - 1;
    }
}

4. Binary Search on Answer

// Find minimum value in [lo, hi] that satisfies a predicate
int lo = minPossible, hi = maxPossible;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (feasible(mid))
        hi = mid;                           // feasible — try smaller
    else
        lo = mid + 1;                       // not feasible — need larger
}
// lo == hi == minimum feasible answer
📝

Choosing the right template: Use lo <= hi when you want an exact match and return inside the loop. Use lo < hi when you want the boundary (first/last/minimum feasible) and the answer is at lo == hi after the loop.

Step 08

Common Problems

These classic LeetCode problems use modified binary search. They are listed in rough order from fundamental to advanced.

#704 Binary Search Easy
#35 Search Insert Position Easy
#34 Find First and Last Position of Element in Sorted Array Medium
#33 Search in Rotated Sorted Array Medium
#153 Find Minimum in Rotated Sorted Array Medium
#1011 Capacity To Ship Packages Within D Days Medium
💡

Practice path: Start with #704 (pure binary search) and #35 (lower bound). Then tackle #34 (two binary searches on one array). Once comfortable, try #33 (rotated) and finally #1011 (search on answer) which tests whether you can construct a feasibility predicate.

Step 09

Interactive Demo

Step through binary search visually. Watch how the search space shrinks by half at each iteration.

⚙ Demo 1: Standard Binary Search on Sorted Array



Press "Step →" or "Run All" to begin.

⚙ Demo 2: Search in Rotated Sorted Array



Press "Step →" or "Run All" to begin.
Step 10

Complexity Analysis

Time
O(log n)
Space
O(1)

Why O(log n)?

Each iteration halves the search space. Starting with n candidates, after 1 step we have n/2, after 2 steps n/4, and after k steps n/2^k. The loop ends when n/2^k = 1, giving k = log2(n) iterations.

Binary search on answer: The time is O(log(range) * C) where range = hi - lo and C is the cost of the feasibility check. For the shipping problem, C = O(n), so total is O(n * log(sum)).

Space: All variants use O(1) extra space — just a few integer variables for lo, hi, and mid.

⚡

Practical impact: For n = 10^9, binary search needs only about 30 iterations. This is why binary search on answer can handle enormous ranges efficiently — the log factor compresses the search space dramatically.

Step 11

Key Takeaways

01

Use lo + (hi - lo) / 2 instead of (lo + hi) / 2. The latter can cause integer overflow when lo and hi are large. The former always produces a valid midpoint. This is a standard interview expectation.

02

Choose your while condition deliberately. Use lo <= hi for exact-match searches where you return inside the loop. Use lo < hi for boundary searches where the answer is at the convergence point lo == hi.

03

Identify the monotonic property. Binary search requires that some property changes from false to true (or vice versa) exactly once across the search space. Finding this "transition boundary" is the key to formulating any binary search problem.

04

Binary search on answer is a meta-technique. Whenever a problem asks "find the minimum X such that...", check if the feasibility predicate is monotonic. If yes, binary search on the answer space and run the feasibility check at each midpoint.

05

Watch for off-by-one errors. The most common bugs in binary search: wrong loop condition, forgetting to include/exclude mid, and infinite loops from lo = mid without rounding up. Always trace through a 2-element array to verify your template.