Pattern 12: Binary Search (Modified)

0. The Template (Copy-Paste Skeleton)

Three skeletons. Template B (find the boundary) is the one to memorise — it solves far more interview problems than the exact-match version, and it never has an off-by-one.

// TEMPLATE A — EXACT MATCH (classic)
int search(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {                          // '<=' : the search space is INCLUSIVE
        int mid = lo + (hi - lo) / 2;           // overflow-safe midpoint
        if (a[mid] == target) return mid;
        else if (a[mid] < target) lo = mid + 1;
        else                      hi = mid - 1;
    }
    return -1;
}

// TEMPLATE B — FIND THE BOUNDARY (first index where the predicate becomes true)
// The array looks like: F F F F T T T T   → find the first T.
int firstTrue(int lo, int hi) {                 // hi is EXCLUSIVE
    while (lo < hi) {                           // '<' and no ±1 on lo → cannot infinite-loop
        int mid = lo + (hi - lo) / 2;
        if (predicate(mid)) hi = mid;           // mid might BE the answer → keep it
        else                lo = mid + 1;       // mid is definitely not → discard it
    }
    return lo;                                  // lo == hi == the first index where it's true
}

// TEMPLATE C — BINARY SEARCH ON THE ANSWER (the array isn't what you search)
int minFeasible(int loAns, int hiAns) {
    while (loAns < hiAns) {
        int mid = loAns + (hiAns - loAns) / 2;
        if (canDo(mid)) hiAns = mid;            // feasible → try something smaller
        else            loAns = mid + 1;        // infeasible → must go bigger
    }
    return loAns;
}
// canDo(x) is an O(n) greedy simulation. Total: O(n log(range)).

Template B is a Swiss army knife — just change the predicate

Want	Predicate
first index with a[i] >= target (lower bound)	a[mid] >= target
first index with a[i] > target (upper bound)	a[mid] > target
last index with a[i] <= target	firstTrue(a[mid] > target) - 1
first bad version (LC 278)	isBadVersion(mid)
min capacity to ship in D days (LC 1011)	daysNeeded(mid) <= D
min eating speed (LC 875)	hoursNeeded(mid) <= H
smallest divisor / split array largest sum	feasible(mid)

The rules that kill every off-by-one

1. lo + (hi - lo) / 2, never (lo + hi) / 2 — the latter overflows int once both exceed ~1.07 billion. Free senior signal; say why.
2. Pair the bracket with the guard: inclusive hi = n - 1 ⇒ while (lo <= hi); exclusive hi = n ⇒ while (lo < hi). Mixing them is where infinite loops come from.
3. In Template B, never write lo = mid. With lo = mid and a 2-element range, mid rounds down to lo and nothing changes → infinite loop. It’s hi = mid / lo = mid + 1.
4. Rotated sorted array: one half is always sorted. Determine which (a[lo] <= a[mid]), then check whether the target lies inside that sorted half.

The trigger you’ll miss if you’re not looking

Binary search does not require a sorted array — it requires a monotonic predicate. Whenever the answer space has the shape “everything below X fails, everything at or above X works”, you can binary search it. That’s the whole of Template C: LC 875, 1011, 410, 1482.

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• Input is sorted (or has a sorted property like rotated sorted)
• “Find the boundary” or “minimum value that satisfies”
• “Search in rotated sorted array”
• Time complexity needs to be O(log n)
• “Peak element” or “mountain array”

The Algorithm (Pseudocode)

Classic Binary Search:

left = 0, right = n - 1

while left <= right:
    mid = left + (right - left) / 2   // avoid overflow

    if arr[mid] == target:
        return mid
    else if arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

return -1

Boundary Binary Search (find first/last occurrence):

left = 0, right = n - 1, result = -1

while left <= right:
    mid = left + (right - left) / 2

    if arr[mid] >= target:   // or <=, depending on first/last
        result = mid
        right = mid - 1      // keep searching left for FIRST
    else:
        left = mid + 1

return result

The ‘Trick’ to Know

• left + (right - left) / 2 instead of (left + right) / 2 to prevent integer overflow.
• Rotated Sorted Array: At least one half is always sorted. Check which half is sorted, then determine if the target falls in that sorted half.
• Search space doesn’t have to be an array: You can binary search on the “answer” (e.g., “minimum capacity to ship in D days”).

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Search in Rotated Sorted Array - LC 33

Brute Force: Linear Scan - O(n)

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }
}

Optimal: Modified Binary Search - O(log n)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) return mid;

            if (nums[left] <= nums[mid]) {
                // Left half is sorted
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // Right half is sorted
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

Java Architecture Insights

• Arrays.binarySearch(): Java’s built-in. Returns -(insertion point) - 1 if not found. Useful but doesn’t handle rotated arrays.
• int mid = left + (right - left) / 2: Standard overflow prevention. With left = 1 billion and right = 2 billion, (left + right) overflows int.
• Why <= in nums[left] <= nums[mid]? The = handles the case when left == mid (only 1-2 elements). Without it, you might recurse into the wrong half.

---

3. Mental Model & Visualization

ASCII Diagram (nums = [4,5,6,7,0,1,2], target = 0)

Step 1: left=0, right=6, mid=3
        [4, 5, 6, |7|, 0, 1, 2]
        nums[0]=4 <= nums[3]=7 → left half sorted
        target 0 not in [4..7) → search right: left=4

Step 2: left=4, right=6, mid=5
        [0, |1|, 2]
        nums[4]=0 <= nums[5]=1 → left half sorted
        target 0 in [0..1) → search left: right=4

Step 3: left=4, right=4, mid=4
        [|0|]
        nums[4]=0 == target → return 4

Senior Mental Trigger

“Sorted + O(log n) = binary search. Not obviously sorted? Check if answer space is monotonic.”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 704	Binary Search	Easy
LC 35	Search Insert Position	Easy
LC 34	Find First and Last Position	Medium
LC 74	Search a 2D Matrix	Medium
LC 278	First Bad Version	Easy

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 33	Search in Rotated Sorted Array	Medium
LC 153	Find Minimum in Rotated Sorted Array	Medium
LC 162	Find Peak Element	Medium
LC 1011	Capacity To Ship Packages Within D Days	Medium
LC 410	Split Array Largest Sum	Hard
LC 4	Median of Two Sorted Arrays	Hard

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
Linear Scan	O(n)	O(1)	Check every element
Binary Search	O(log n)	O(1)	Halve search space each step
Binary on Answer	O(n log M)	O(1)	M = answer range, n = validation