Week 9: Binary Search & The Answer Space

1. Overview

Welcome to Week 9 and the beginning of Phase 3: Core Algorithms! For the last 8 weeks, we focused on where data is stored (arrays, trees, graphs). Now, we shift our focus to how we process that data efficiently.

We begin with Binary Search. While most people know it as "find an element in a sorted array," the true power of this pattern lies in Binary Search on the Answer Space — a technique that lets you search for the optimal value of something (a speed, a capacity, a day count) in $O(\log N)$ time, as long as the problem has a specific mathematical property called monotonicity.

Why Does This Matter?

The jump from $O(N)$ to $O(\log N)$ is staggering at scale:

Array Size	Linear Search $O(N)$	Binary Search $O(\log N)$
1,000	1,000 ops	10 ops
1,000,000	1,000,000 ops	20 ops
1,000,000,000	1,000,000,000 ops	30 ops

Binary search on 1 billion items takes 30 operations. This is why it's used in databases, file systems, and every search engine on the planet.

Goals for this week:

• Understand $O(\log N)$ intuitively and why it scales so dramatically.
• Master standard Binary Search with correct boundary handling.
• Learn the midpoint overflow bug that causes mysterious failures.
• Handle the rotated sorted array — the most common binary search variation.
• Master Binary Search on the Answer Space — a pattern that turns "try everything" brute-forces into elegant $O(\log N)$ solutions.

Knowledge You Need Before Starting

• Sorted-array intuition and boundary-handling rigor from prior weeks.
• Comfort with loop invariants (low, high, and termination conditions).
• Basic monotonic reasoning ("if X works, bigger/smaller also works").
• Integer overflow awareness and safe midpoint formula usage.

---

2. The Core Mental Models

Binary Search Bisecting Search Space

Init: L=0, R=8. Mid = 4 (Value = 14). target 14 == arr[4] → FOUND in 1 comparison!

Search Space Halving: N → N/2 → N/4 → 1. Guarantees O(log N) Time Complexity.

2.1 What Is Binary Search? — The "Encyclopedia" Model

Imagine you're looking up a word in a physical encyclopedia. You don't start from page 1. You open to the middle, check if the word comes before or after, then open to the middle of the relevant half, and repeat.

Each "open" eliminates half the remaining pages. That's binary search.

---

5.2 Keyword Trigger Table

Problem Keywords	Technique	Template
"sorted array" + "find target"	Standard binary search	Template 1
"first/last occurrence" / "leftmost/rightmost"	Boundary binary search	Template 2
"find minimum in rotated sorted array"	Rotated binary search	Template 4
"search in rotated sorted array"	Rotated binary search	Template 4
"minimize the maximum"	Binary search on answer space	Template 3
"maximize the minimum"	Binary search on answer space	Template 3
"minimum speed/capacity/days to finish"	Binary search on answer space	Template 3
"split array into K parts" with min/max	Binary search on answer space	Template 3
"must run in O(log N)"	Binary search (some variant)	—
"find peak element"	Binary search (find local max)	Template B
"sqrt(x)" / "nth root"	Binary search on answer space	Template 3
"k-th smallest in sorted matrix"	Binary search on value space	Template 3

---

5.3 Common Traps & How to Avoid Them

Trap 1: Integer overflow in midpoint calculation

// ❌ Overflows when left + right > 2,147,483,647
int mid = (left + right) / 2;

// ✅ Safe always
int mid = left + (right - left) / 2;

---

Trap 2: Wrong boundary initialization for Answer Space

// Koko Eating Bananas:
// ❌ right = piles.length  (number of piles, not max pile size!)
int right = piles.length;

// ✅ right = max(piles) (Koko never needs to eat faster than the biggest pile)
int right = 0;
for (int p : piles) right = Math.max(right, p);

---

Trap 3: Infinite loop from wrong boundary update

// ❌ Forgetting to exclude mid — infinite loop when left == right
if (isValid(mid)) {
    right = mid;    // Never shrinks if mid == right!
} else {
    left = mid;     // Never shrinks if mid == left!
}

// ✅ Always move past mid
if (isValid(mid)) {
    result = mid;
    right = mid - 1;   // Exclude mid, shrink left
} else {
    left = mid + 1;    // Exclude mid, shrink right
}

---

Trap 4: Using floating point in the helper function

// ❌ Floating point — precision risk for large values, slower
long hours = (long) Math.ceil((double) job / k);

// ✅ Integer ceiling — exact and fast
long hours = (long)(job + k - 1) / k;

---

Trap 5: Wrong condition for rotated array — < vs <=

// In rotated array search, checking which half is sorted:
// ❌ Strict less-than misses the case when left == mid (single element)
if (nums[left] < nums[mid]) { ... }

// ✅ Must use <= to handle the single-element case correctly
if (nums[left] <= nums[mid]) {
    // Left half [left..mid] is sorted
}

---

Trap 6: Not using long in the helper function

// If jobs[i] up to 10^9 and there are 10^5 jobs:
// Total seconds could be up to 10^14 — overflows int (max ~2×10^9)!
// ❌
int secondsRequired = 0;
for (int job : jobs) secondsRequired += (job + cores - 1) / cores;

// ✅ Use long
long secondsRequired = 0;
for (int job : jobs) secondsRequired += (long)(job + cores - 1) / cores;

---

Trap 7: Forgetting the early exit in the helper function

// For large inputs, this optimization matters:
private boolean canFinish(int[] jobs, int capacity, int deadline) {
    long total = 0;
    for (int job : jobs) {
        total += (long)(job + capacity - 1) / capacity;
        if (total > deadline) return false;  // Early exit!
        // Without this, you compute the full sum even when it's already too large
    }
    return true;
}

---

6. Worked Examples (Step-by-Step Walkthroughs)

Example 1: LeetCode 704 — Binary Search

Problem: Find target in a sorted array. Return its index or -1.

Thought process:

1. Array is sorted → Binary Search.
2. Each step: compare mid to target, eliminate half the search space.
3. Loop condition: left <= right (both ends inclusive, terminate when range is empty).

nums = [-1, 0, 3, 5, 9, 12],  target = 9

left=0, right=5, mid=2 → nums[2]=3 < 9 → search right → left=3
left=3, right=5, mid=4 → nums[4]=9 == 9 → FOUND at index 4 ✅

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;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

Complexity: Time $O(\log N)$, Space $O(1)$.

---

Example 2: LeetCode 33 — Search in Rotated Sorted Array

Problem: Array was sorted and then rotated at an unknown pivot. Find target in $O(\log N)$.

Thought process:

1. Can't do standard binary search — array isn't fully sorted.
2. Key insight: At every mid, one half is always fully sorted. Find which one, check if target is in it, then eliminate the other.
3. If left half [left..mid] is sorted: check if target falls in [nums[left]..nums[mid]).
4. Otherwise, right half [mid..right] is sorted: check if target falls in (nums[mid]..nums[right]].

nums = [4, 5, 6, 7, 0, 1, 2],  target = 0

left=0, right=6, mid=3 → nums[3]=7
  Left half [4,5,6,7]: sorted? nums[0]=4 <= nums[3]=7? YES
  Is target(0) in [4..7)? 0 >= 4? NO → search right half
  left = 4

left=4, right=6, mid=5 → nums[5]=1
  Left half [0,1]: sorted? nums[4]=0 <= nums[5]=1? YES
  Is target(0) in [0..1)? 0 >= 0 AND 0 < 1? YES → search left half
  right = 4

left=4, right=4, mid=4 → nums[4]=0 == 0 → FOUND at index 4 ✅

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;  // Target in sorted left half
                } else {
                    left = mid + 1;   // Target in right half
                }
            } else {
                // Right half is sorted
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;   // Target in sorted right half
                } else {
                    right = mid - 1;  // Target in left half
                }
            }
        }
        return -1;
    }
}

---

Example 3: LeetCode 875 — Koko Eating Bananas

Problem: Koko has n piles of bananas and h hours. Find the minimum speed k (bananas/hour) to eat all piles within h hours. Each hour she picks one pile and eats up to k bananas from it.

Thought process:

1. "Minimum speed to finish within deadline" → Binary Search on Answer Space.
2. Monotonicity: If speed k works, speed k+1 definitely works (faster = fewer hours). ✅
3. Search range: left = 1 (minimum speed), right = max(piles) (never need to eat faster than the biggest pile — she can't eat from multiple piles in one hour).
4. For each candidate speed k, compute total hours needed. If ≤ h, record and try smaller.

piles = [3, 6, 7, 11],  h = 8

left=1, right=11 (max pile)

mid=6: hours = ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6)
             = 1 + 1 + 2 + 2 = 6 ≤ 8 ✅ → result=6, right=5

mid=3: hours = ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3)
             = 1 + 2 + 3 + 4 = 10 > 8 ❌ → left=4

mid=4: hours = ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4)
             = 1 + 2 + 2 + 3 = 8 ≤ 8 ✅ → result=4, right=3

left=4 > right=3 → STOP

Answer: 4 ✅

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 0;
        for (int pile : piles) right = Math.max(right, pile);

        int result = right;  // Default: eat as fast as possible

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

            if (canFinish(piles, k, h)) {
                result = k;       // Valid speed found, record it
                right = k - 1;   // Try slower
            } else {
                left = k + 1;    // Too slow, try faster
            }
        }

        return result;
    }

    private boolean canFinish(int[] piles, int k, int h) {
        long hours = 0;
        for (int pile : piles) {
            hours += (pile + k - 1) / k;  // Ceiling division
            if (hours > h) return false;   // Early exit
        }
        return hours <= h;
    }
}

Complexity: Time $O(N \log M)$ where $M = max(piles)$. Space $O(1)$.

---

Example 4: LeetCode 410 — Split Array Largest Sum

Problem: Split nums into k non-empty subarrays. Minimize the largest subarray sum.

Thought process:

1. "Minimize the maximum" → Binary Search on Answer Space.
2. Monotonicity: If we can split with maximum sum ≤ X, we can also split with maximum sum ≤ X+1. ✅
3. Search range: left = max(nums) (each subarray must have at least one element), right = sum(nums) (one subarray = the whole array).
4. Helper: given a maximum allowed sum mid, can we split the array into at most k parts?

nums = [7, 2, 5, 10, 8],  k = 2

left = max(nums) = 10,  right = sum(nums) = 32

mid = 21:
  Greedy split: [7,2,5] (sum=14 ≤ 21), [10,8] (sum=18 ≤ 21) → 2 parts ≤ k=2 ✅
  result=21, right=20

mid = 15:
  [7,2,5] (sum=14 ≤ 15), [10] (sum=10 ≤ 15), [8] — oops, already 3 parts
  Wait: [7,2,5,10]? sum=24 > 15, so can't include 10 with 7,2,5.
  [7,2,5] (14), [10] (10), [8] (8) → 3 parts > k=2 ❌
  left=16

mid = 18:
  [7,2,5] (14 ≤ 18), then add 10: 14+10=24 > 18 → new part
  [10] (10 ≤ 18), then add 8: 10+8=18 ≤ 18 → same part
  [10,8] (18) → 2 parts ≤ k=2 ✅
  result=18, right=17

mid = 16: left=16, right=17, mid=16
  [7,2,5] (14), then 10: 14+10=24>16 → [10], then 8: 10+8=18>16 → [8]
  3 parts > 2 ❌ → left=17

mid = 17: left=17, right=17
  [7,2,5] (14), then 10: 24>17 → [10], then 8: 10+8=18>17 → [8]
  3 parts > 2 ❌ → left=18

left=18 > right=17 → STOP

Answer: 18 ✅

class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0, right = 0;
        for (int n : nums) {
            left = Math.max(left, n);   // Must be at least max element
            right += n;                  // At most the full sum
        }

        int result = right;

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

            if (canSplit(nums, k, mid)) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return result;
    }

    private boolean canSplit(int[] nums, int k, int maxSum) {
        int parts = 1;
        long currentSum = 0;

        for (int num : nums) {
            if (currentSum + num > maxSum) {
                parts++;                   // Start a new part
                currentSum = num;
                if (parts > k) return false;  // Too many splits
            } else {
                currentSum += num;
            }
        }
        return true;
    }
}

---

7. Problem-Solving Framework (Use This in Interviews)

Step 1 — Identify Binary Search Applicability (30 seconds)

Ask yourself:

"Is the input sorted? Or are the possible answers ordered/rankable?"

"Is there a yes/no condition with a monotonic threshold?"

"Does the problem say $O(\log N)$?"

Step 2 — Classify the Problem (30 seconds)

"Am I searching for a specific value in a sorted array?" → Standard (Template 1)

"Am I finding the first/last occurrence of something?" → Boundary search (Template 2)

"Am I minimizing/maximizing a threshold value?" → Answer Space (Template 3)

"Is the array rotated?" → Rotated search (Template 4)

Step 3 — Define Boundaries (say this out loud)

"The minimum possible answer is X because [reason]. The maximum is Y because [reason]. My result variable starts at Y (worst case)."

Step 4 — Write and Justify the Helper Function

"My helper isValid(mid) checks whether mid satisfies the constraint. I'll use integer ceiling division to avoid floating-point precision issues. I'll also add an early exit if the total exceeds the deadline to optimize for large inputs."

Step 5 — Test Edge Cases Out Loud

For standard binary search:

• Array of length 1 (target present / absent)
• Target at index 0 or n-1 (boundary values)
• All elements are the same

For answer space:

• All jobs the same size
• One job that's enormous relative to the deadline
• Deadline exactly equals the number of jobs (minimum possible scenario)

---

8. 7-Day Practice Plan (21 Problems)

Day 1: Binary Search Fundamentals

1. Binary Search (LC 704) — Write from memory, no peeking
2. Search Insert Position (LC 35) — When not found: where would it go?
3. First Bad Version (LC 278) — Boundary search: find first "bad"

Day 1 Focus: After solving LC 704, close everything and rewrite it from scratch. The template must be in muscle memory before you tackle variations.

Day 2: Searching in 2D Matrices 4. Search a 2D Matrix (LC 74) — Treat as 1D sorted array via index math 5. Search a 2D Matrix II (LC 240) — Staircase search: start top-right corner 6. Count Negative Numbers in a Sorted Matrix (LC 1351) — Binary search per row

Day 2 Focus: LC 74 and LC 240 look similar but need different approaches. LC 74: the entire matrix is one sorted sequence. LC 240: rows and columns are sorted separately → the top-right corner trick (go left if too big, go down if too small).

Day 3: Handling Rotated Arrays 7. Find Minimum in Rotated Sorted Array (LC 153) — Find the "drop point" 8. Search in Rotated Sorted Array (LC 33) — Full rotated search 9. Find Minimum in Rotated Sorted Array II (LC 154) — With duplicates: O(N) worst case

Day 3 Focus: LC 154 has duplicates. When nums[left] == nums[mid], you can't determine which half is sorted — you must do left++ to skip the duplicate. Acknowledge this degrades to $O(N)$ worst case.

Day 4: Ranges & Frequencies 10. Find First and Last Position of Element in Sorted Array (LC 34) — Two binary searches: leftmost and rightmost 11. Single Element in a Sorted Array (LC 540) — Parity-based binary search 12. Find Peak Element (LC 162) — Binary search on local max: go toward the uphill side

Day 4 Focus: LC 540 is subtle. Before the single element, pairs are at (even, odd) indices. After it, pairs are at (odd, even) indices. This parity shift is the binary search condition.

Day 5: Introduction to Answer Space 13. Koko Eating Bananas (LC 875) — The gateway answer space problem 14. Capacity To Ship Packages Within D Days (LC 1011) — Same template, different story 15. Minimum Number of Days to Make m Bouquets (LC 1482) — Helper needs adjacent counting

Day 5 Focus: After solving LC 875 and LC 1011, notice how identical the structure is. The only difference is the helper function. This is the pattern: identify search space + write one helper = done.

Day 6: Advanced Answer Space Patterns 16. Split Array Largest Sum (LC 410) — "Minimize the maximum" — the canonical answer space 17. Maximum Number of Removable Characters (LC 1898) — Binary search on how many to remove 18. Kth Smallest Element in a Sorted Matrix (LC 378) — Binary search on value, not index

Day 6 Focus: LC 378 searches on the value space, not the index space. The helper counts how many elements are ≤ mid. This is a more abstract form of the answer space pattern — worth spending extra time on.

Day 7: Math & System Design 19. Sqrt(x) (LC 69) — Classic: find largest x where x² ≤ n 20. Valid Perfect Square (LC 367) — Variation of LC 69 21. Time Based Key-Value Store (LC 981) — Binary search in a real system design context using TreeMap

Day 7 Focus: LC 981 combines system design (a key-value store with timestamps) with binary search. It's a great preview of how binary search appears in production systems, not just algorithmic puzzles.

---

9. Mock Interview Module

Problem: The Distributed Batch Processor

Context: A cloud platform auto-scaler receives a list of jobs (each job requires jobs[i] million instructions). Each core processes exactly 1 million instructions/second. If a job finishes before the second is up, the core idles until the next second. Find the minimum number of cores to finish all jobs within a deadline in seconds.

Question: public int minCoresRequired(int[] jobs, int deadline)

---

Step 1: Clarifying Questions

• Candidate: "If deadline < jobs.length, is it impossible?" → Interviewer: Yes, return -1. Each job takes at least 1 second.
• Candidate: "Can jobs[i] be 0?" → Interviewer: No, all jobs require at least 1 instruction.
• Candidate: "Should I use long for intermediate calculations?" → Interviewer: Good catch — yes. Jobs can be up to $10^9$ and there can be $10^5$ of them, so totals can reach $10^14$.
• Candidate: "Are cores assigned exclusively to one job at a time?" → Interviewer: Yes, one core processes one job per second increment.

---

Step 2: Formulating the Strategy

Candidate's thought process out loud:

1. "The answer (number of cores) ranges from 1 to max(jobs). That's up to $10^9$ possible answers — we can't check linearly."
2. "Is there monotonicity? If $X$ cores can meet the deadline, will $X+1$ cores also meet it? Yes — more cores means jobs finish faster. So the answer space is monotonic."
3. "I'll binary search the answer space from 1 to max(jobs). For each candidate core count, I'll compute total seconds needed. If ≤ deadline, that core count works."
4. "The total seconds for c cores on a job of size j is ceil(j/c) = (j+c-1)/c."

---

Step 3: Optimized Solution

public int minCoresRequired(int[] jobs, int deadline) {
    if (deadline < jobs.length) return -1;  // Impossible: each job needs ≥ 1 second

    int left = 1;
    int right = 0;
    for (int job : jobs) right = Math.max(right, job);  // Upper bound: max job size

    int result = right;  // Default: max possible

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

        if (canMeetDeadline(jobs, mid, deadline)) {
            result = mid;        // Valid — record it
            right = mid - 1;    // Try fewer cores (save money)
        } else {
            left = mid + 1;     // Too slow — need more cores
        }
    }

    return result;
}

private boolean canMeetDeadline(int[] jobs, int cores, long deadline) {
    long secondsRequired = 0;
    for (int job : jobs) {
        secondsRequired += (long)(job + cores - 1) / cores;  // Ceiling division
        if (secondsRequired > deadline) return false;         // Early exit
    }
    return secondsRequired <= deadline;
}

Talk through this in the interview:

"The search space is [1, max(jobs)]. Binary search runs in $O(\log(\max(jobs)))$ = $O(\log(10^9))$ ≈ 30 iterations. Each iteration calls the helper which runs in $O(N)$. Total: $O(N \log(\max(jobs)))$ — efficient even for $10^5$ jobs with sizes up to $10^9$."

---

Step 4: Follow-up Questions

Follow-up 1 (Integer math): Interviewer: "Why use (job + cores - 1) / cores instead of Math.ceil((double) job / cores)?"

Expected answer:

• Floating-point arithmetic involves converting integers to IEEE 754 doubles, performing the division, and rounding — all slower than pure integer math.
• More critically, for large values like job = 10^9, casting to double loses precision (doubles have ~15 significant digits; 10^9 is fine, but compound calculations can drift).
• The integer ceiling formula (a + b - 1) / b is mathematically equivalent to ceil(a/b) for positive integers, is exact, and is faster.

Follow-up 2 (Dynamic workload): Interviewer: "What if jobs arrive in a streaming fashion and you need to continuously recommend the minimum cores in real-time as new jobs arrive?"

Expected thought process:

• Rerunning binary search for each new job: $O(N \log M)$ per arrival. For $K$ arrivals, $O(KN \log M)$ total.
• Optimization: maintain a running max (maxJob) and sum (totalSeconds at the current optimal core count). When a new job arrives, incrementally update.
• If the new job increases maxJob, the upper bound shifts — re-run binary search. Otherwise, just check if the current core count still works by updating the helper.
• For a production system: pre-warm the binary search and use exponential backoff on the upper bound — start with current right, double if needed, then binary search between old and new bounds.

Follow-up 3 (Multi-dimension): Interviewer: "Now each job has both a CPU requirement AND a memory requirement. Find the minimum number of cores that satisfies BOTH the deadline for CPU AND stays within a memory budget."

Expected thought process:

• Two constraints means the feasibility check (canMeetDeadline) must now validate both conditions.
• The monotonicity still holds: more cores → fewer seconds (CPU) AND each core has a fixed memory footprint (memory = cores × per-core-memory).
• Binary search on cores still works — just extend the helper to check both conditions.
• If constraints conflict (e.g., CPU needs 100 cores but memory only allows 10), return -1.

---

10. Connecting to Other Weeks

Binary Search is uniquely versatile — it connects backward and forward across the entire roadmap:

Week 2 (Two Pointers) + Week 9 (Binary Search):
  → Both exploit sorted/ordered structure
  → Two pointers: O(N) on a sorted array
  → Binary search: O(log N) when you can eliminate half per step
  → Rule: if you can eliminate half → binary search beats two pointers

Week 6 (Trees) + Week 9 (Binary Search):
  → Binary Search Tree (BST) IS binary search applied to a tree
  → BST search: O(log N) on average — same halving principle
  → Lower bound on sorted array = floor() in a BST

Week 9 (Binary Search) + Week 10+ (Dynamic Programming):
  → Many DP optimizations use binary search (Longest Increasing Subsequence in O(N log N))
  → "Patience sorting" — DP + binary search on the answer
  → Binary search helps reduce DP from O(N²) to O(N log N)

Week 9 (Binary Search on Answer Space) + System Design:
  → Load balancers use binary search to find optimal server assignment
  → Database indexing (B-trees) is binary search generalized to disk storage
  → Rate limiting: binary search on time windows

---

11. Quick Reference Cheat Sheet

╔══════════════════════════════════════════════════════════════╗
║           BINARY SEARCH CHEAT SHEET                         ║
╠══════════════════════════════════════════════════════════════╣
║ ALWAYS USE SAFE MIDPOINT                                     ║
║   int mid = left + (right - left) / 2;                      ║
╠══════════════════════════════════════════════════════════════╣
║ STANDARD BINARY SEARCH                                       ║
║   while (left <= right)                                      ║
║   Found: return mid                                          ║
║   Too small: left = mid + 1                                  ║
║   Too large: right = mid - 1                                 ║
║   Not found: return -1                                       ║
╠══════════════════════════════════════════════════════════════╣
║ ANSWER SPACE BINARY SEARCH                                   ║
║   left = minimum possible answer                             ║
║   right = maximum possible answer                            ║
║   result = right  (default worst case)                       ║
║   if isValid(mid): result=mid; right=mid-1  (try smaller)   ║
║   else: left=mid+1  (need bigger)                           ║
╠══════════════════════════════════════════════════════════════╣
║ INTEGER CEILING DIVISION                                     ║
║   ceil(a/b) = (a + b - 1) / b   (for positive a, b)        ║
║   Never use (double) cast for large values!                  ║
╠══════════════════════════════════════════════════════════════╣
║ ROTATED ARRAY                                                ║
║   Left sorted if: nums[left] <= nums[mid]                   ║
║   Use <=  not  < to handle single-element case              ║
╠══════════════════════════════════════════════════════════════╣
║ MONOTONICITY CHECK                                           ║
║   "If X works, does X+1 also work?" → YES → Answer Space   ║
║   "Minimize the maximum" / "Maximize the minimum" → YES     ║
╠══════════════════════════════════════════════════════════════╣
║ OVERFLOW RISK                                                ║
║   Use long in helper when sum can exceed ~2×10^9            ║
║   Add early exit: if (total > deadline) return false        ║
╠══════════════════════════════════════════════════════════════╣
║ COMPLEXITY                                                   ║
║   Standard: O(log N) time, O(1) space                      ║
║   Answer space: O(N log M) where M = answer range size      ║
╚══════════════════════════════════════════════════════════════╝

---

12. What's Coming Next

Week 10: Dynamic Programming (DP) — the next leap in algorithmic thinking:

• Binary search and DP often combine: the Longest Increasing Subsequence can be solved in $O(N \log N)$ using binary search on a DP array (patience sorting).
• The "answer space" mindset from this week carries directly into DP: "what is the minimum cost to reach state X?" is the same kind of optimization question, solved by exhaustive subproblem decomposition instead of binary search.

Week 11+: Greedy Algorithms — sometimes the local optimum IS the global optimum:

• Many problems that appear to need binary search on the answer space can be solved greedily if you can prove that always picking the locally optimal choice leads to a globally optimal result.
• The key skill: knowing when to binary search (monotonic threshold) vs when to greedy (provably optimal local choice).

The meta-skill binary search teaches: Whenever you see a brute-force "try all values from 1 to N," ask: "Is there a monotonic threshold?" If yes, you've just turned an $O(N)$ or $O(N^2)$ solution into $O(\log N)$ or $O(N \log N)$. This reflex will serve you in almost every domain of algorithm design.