lthieu's notes

04-Advanced-Binary-Search

14 min read

Buổi 04 — Advanced Binary Search

Navigation

← 03-Monotonic-Stack-Queue | → 05-Divide-and-Conquer Giai đoạn: FAANG Mastery | Độ khó: ⭐⭐⭐⭐

1. Analogy & Context

Baking Temperature Analogy

“Binary Search on the Answer” = thay vì tìm kiếm một VALUE trong sorted array, bạn tìm kiếm chính CÂU TRẢ LỜI trong không gian giá trị của nó.

Tưởng tượng bạn cần tìm nhiệt độ tối ưu để nướng bánh mì:

  • Bạn biết nhiệt độ nằm trong khoảng 100°C – 300°C
  • Với mỗi nhiệt độ bạn chọn, bạn có thể kiểm tra “có đủ tốt không?” trong O(1)
  • Không cần thử hết 200 nhiệt độ → binary search nhiệt độ!

Key insight: Không gian câu trả lời có tính monotonic — nếu nhiệt độ X “đủ tốt”, thì X+1 cũng “đủ tốt” (hoặc ngược lại). Tính chất này cho phép binary search.

Classic Binary Search vs Binary Search on Answer:

ClassicOn Answer
Tìm VALUE trong sorted arrayTìm ANSWER trong range [lo, hi]
Array đã sắp xếp sẵnKhông gian answer có tính monotonic
O(log N)O(N log(range)) — N cho check, log cho search
”Is target at index mid?""Is mid a feasible answer?”

L5 → L6 Differentiator

Đây là kỹ thuật phân biệt Senior Engineer với Mid-level. Bài toán trông có vẻ cần O(N²) brute force, nhưng khi nhận ra “answer space is monotonic” → O(N log N) solution hiện ra.

2. The FAANG Standard

Framework tổng quát:

1. Xác định không gian answer: [lo, hi]
   - lo = giá trị nhỏ nhất có thể (often 1 or min(array))
   - hi = giá trị lớn nhất có thể (often max(array) or sum(array))

2. Viết hàm check(mid): có thể đạt được với answer = mid không?
   - Hàm này phải chạy trong O(N) hoặc O(N log N)
   - Hàm PHẢI monotonic: false...false...true...true (hoặc ngược lại)

3. Binary search trên [lo, hi]:
   - Find first true (minimize): lo=mid+1 khi check fails
   - Find last true (maximize): hi=mid-1 khi check fails

Các dạng bài phổ biến:

Problem Typelohicheck(mid)
Koko Bananas1max(piles)Ăn hết trong H giờ không?
Min Days Bouquets1max_daysĐủ bouquets sau mid ngày không?
Capacity to Shipmax(weights)sum(weights)Ship hết trong D ngày không?
Split Array Largest Summax(array)sum(array)Chia thành m phần, max ≤ mid không?
Kth Smallest Matrixmatrix[0][0]matrix[n-1][n-1]Có ≥ k elements ≤ mid không?

3. Visual Thinking (Mermaid)

3.1 Monotonic Predicate Concept

graph LR
    subgraph "Answer Space [lo ... hi]"
        direction LR
        F1["lo: ❌"] --> F2["❌"] --> F3["❌"] --> T1["✅ ← first true"] --> T2["✅"] --> T3["hi: ✅"]
    end

    style T1 fill:#22c55e,color:#fff
    style F1 fill:#ef4444,color:#fff
    style F2 fill:#ef4444,color:#fff
    style F3 fill:#ef4444,color:#fff
    style T2 fill:#22c55e,color:#fff
    style T3 fill:#22c55e,color:#fff

flowchart TD
    A["Binary Search on [lo=1, hi=max]"] --> B{"check(mid)?"}
    B -->|"false — mid too small"| C["lo = mid + 1"]
    B -->|"true — mid feasible"| D["hi = mid - 1<br/>(try smaller — minimize)"]
    C --> E["Converge to first TRUE"]
    D --> E
    E --> F["Answer = lo"]

    style A fill:#4a9eff,color:#fff
    style F fill:#22c55e,color:#fff

3.2 Binary Search on Answer for Min Days to Make Bouquets

sequenceDiagram
    participant BS as Binary Search
    participant CF as check(mid=days)

    Note over BS: bloomDay=[1,10,3,10,2], m=3 bouquets, k=1 flower each
    Note over BS: lo=1, hi=10

    BS->>CF: check(mid=5)
    Note over CF: After 5 days: [1,_,3,_,2] → 3 consecutive? No, only [1],[3],[2] non-consecutive
    CF-->>BS: false → lo=6

    BS->>CF: check(mid=8)
    Note over CF: After 8 days: [1,_,3,_,2] same... wait, only days≤8 bloom
    Note over CF: bloomed at days[0]=1,days[2]=3,days[4]=2 → 3 flowers → 3 bouquets ✓
    CF-->>BS: true → hi=7

    BS->>CF: check(mid=6)
    Note over CF: Same — 3 flowers bloom by day 6 ✓
    CF-->>BS: true → hi=5

    Note over BS: lo=6 > hi=5 → STOP, answer = lo = 3

3.3 Rotated Array — Which Half is Sorted?

graph TD
    A["nums=[4,5,6,7,0,1,2], target=0"] --> B{"nums[mid] vs nums[lo]"}
    B -->|"nums[mid]=7 >= nums[lo]=4<br/>Left half [4..7] is SORTED"| C{"target in left?"}
    C -->|"0 NOT in [4,7]"| D["Go RIGHT: lo=mid+1"]
    D --> E["nums=[0,1,2], mid=1"] --> F{"nums[mid]=1 >= nums[lo]=0<br/>Left sorted"}
    F -->|"target=0 in [0,1]"| G["Go LEFT: hi=mid-1"]
    G --> H["nums=[0], found at idx=4"]

    style H fill:#22c55e,color:#fff

4. TypeScript Template

4.1 Universal Binary Search Template

// ============================================================
// UNIVERSAL BINARY SEARCH TEMPLATE
// Find: smallest mid where check(mid) = true  (minimize the answer)
// ============================================================
function binarySearchTemplate(
    lo: number,
    hi: number,
    check: (mid: number) => boolean
): number {
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);  // avoid overflow
 
        if (check(mid)) {
            hi = mid;           // mid is feasible, try smaller → hi = mid
        } else {
            lo = mid + 1;       // mid not feasible, need larger → lo = mid+1
        }
    }
    return lo;  // first value where check(lo) = true
}
 
// For MAXIMIZE (last true): swap the hi/lo updates
function binarySearchMaximize(
    lo: number,
    hi: number,
    check: (mid: number) => boolean
): number {
    while (lo < hi) {
        const mid = lo + Math.ceil((hi - lo) / 2);  // NOTE: ceiling to avoid infinite loop
 
        if (check(mid)) {
            lo = mid;           // mid is feasible, try larger
        } else {
            hi = mid - 1;       // mid not feasible, must be smaller
        }
    }
    return lo;
}

4.2 Koko Eating Bananas — O(N log M)

// LeetCode #875
// Binary search on eating speed k (1 to max(piles))
// check(k): can Koko eat all piles within h hours at speed k?
function minEatingSpeed(piles: number[], h: number): number {
    const lo = 1;
    const hi = Math.max(...piles);
 
    // check: with speed=k, total hours = sum of ceil(pile/k)
    const canFinish = (k: number): boolean => {
        let hours = 0;
        for (const pile of piles) {
            hours += Math.ceil(pile / k);
        }
        return hours <= h;
    };
 
    return binarySearchTemplate(lo, hi, canFinish);
}
 
// Example: piles = [3,6,7,11], h = 8
// lo=1, hi=11
// check(6): ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6 <= 8 ✓
// check(3): ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3) = 1+2+3+4 = 10 > 8 ✗
// Answer: 4

4.3 Minimum Days to Make M Bouquets — O(N log D)

// LeetCode #1482
function minDays(bloomDay: number[], m: number, k: number): number {
    const n = bloomDay.length;
 
    // Edge case: not enough flowers total
    if (m * k > n) return -1;
 
    const lo = 1;
    const hi = Math.max(...bloomDay);
 
    // check(day): can we make m bouquets after 'day' days?
    // Each bouquet needs k ADJACENT flowers that have bloomed by 'day'
    const canMake = (day: number): boolean => {
        let bouquets = 0;
        let consecutive = 0;
 
        for (let i = 0; i < n; i++) {
            if (bloomDay[i] <= day) {
                consecutive++;
                if (consecutive === k) {
                    bouquets++;
                    consecutive = 0;    // reset for next bouquet
                }
            } else {
                consecutive = 0;        // streak broken
            }
        }
        return bouquets >= m;
    };
 
    return binarySearchTemplate(lo, hi, canMake);
}

4.4 Split Array Largest Sum — O(N log S)

// LeetCode #410 — See Section 8 for complete solution

4.5 Kth Smallest in Sorted Matrix — O(N log(max-min))

// LeetCode #378
// Key: binary search on VALUE space, not index space!
// check(mid): how many elements in matrix are <= mid?
function kthSmallest(matrix: number[][], k: number): number {
    const n = matrix.length;
    const lo = matrix[0][0];
    const hi = matrix[n - 1][n - 1];
 
    // Count elements <= mid using sorted property (O(N) with two-pointer on rows)
    const countLE = (mid: number): number => {
        let count = 0;
        let col = n - 1;    // start from top-right corner
 
        for (let row = 0; row < n; row++) {
            while (col >= 0 && matrix[row][col] > mid) col--;
            count += col + 1;   // all elements in this row up to col are <= mid
        }
        return count;
    };
 
    // Find smallest value v such that count(v) >= k
    return binarySearchTemplate(lo, hi, (mid) => countLE(mid) >= k);
}
 
// Note: The answer IS in the matrix (not necessarily mid itself).
// binarySearchTemplate finds the exact value because when lo=hi,
// it must be an actual element (proven by invariant).

4.6 Search in Rotated Sorted Array — O(log N)

// LeetCode #33
// Key insight: one half is ALWAYS sorted. Use that to determine which side target is in.
function searchRotated(nums: number[], target: number): number {
    let lo = 0, hi = nums.length - 1;
 
    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
 
        if (nums[mid] === target) return mid;
 
        // Left half [lo..mid] is sorted
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) {
                hi = mid - 1;   // target in left sorted half
            } else {
                lo = mid + 1;   // target in right half (possibly rotated)
            }
        }
        // Right half [mid..hi] is sorted
        else {
            if (nums[mid] < target && target <= nums[hi]) {
                lo = mid + 1;   // target in right sorted half
            } else {
                hi = mid - 1;   // target in left half (possibly rotated)
            }
        }
    }
 
    return -1;
}

5. Complexity Deep-dive

Key Complexity Insight

Nếu check function chạy O(N), thì binary search on answer chạy O(N × 30) = O(N log(max_val)). Với N = 10^5 và max_val = 10^9: chỉ cần khoảng 3 × 10^6 operations — cực kỳ nhanh!

ProblemTimeSpaceBottleneck
Koko Eating BananasM = max(piles)
Min Days BouquetsD = max(bloomDay)
Capacity to ShipS = sum(weights)
Split Array Largest SumS = sum(array)
Kth Smallest MatrixMatrix range
Search Rotated ArrayClassic binary search

So sánh với Brute Force:

  • Split Array Largest Sum: DP solution O(N²·M) vs Binary Search O(N log S)
  • Với N=1000, M=50: DP = 50,000,000 vs Binary Search ≈ 30,000 operations

6. Edge Cases & Pitfalls

Predicate Must Be Monotonic

Binary search on answer chỉ đúng khi predicate có tính monotonic: false, false, ..., false, true, true, ..., true

Nếu pattern là false, true, false, true → không thể dùng binary search! Luôn verify tính monotonic bằng cách chứng minh: “nếu check(x) = true thì check(x+1) = true”.

Getting the Boundary Right

Hai variants boundary quan trọng:

// MINIMIZE (find first true):
if (check(mid)) hi = mid;      // mid might be answer, don't exclude it
else            lo = mid + 1;  // mid definitely not answer
// Final answer: lo
 
// MAXIMIZE (find last true):
if (check(mid)) lo = mid;      // mid might be answer
else            hi = mid - 1;  // mid definitely not answer
// Use: mid = lo + Math.ceil((hi-lo)/2)  ← ceiling avoids infinite loop!
// Final answer: lo (= hi)

Integer vs Float Binary Search

Float binary search cần epsilon thay vì lo < hi:

// Float binary search:
let lo = 0.0, hi = 1e9;
const eps = 1e-7;
while (hi - lo > eps) {         // NOT hi > lo (infinite loop!)
    const mid = (lo + hi) / 2;
    if (check(mid)) hi = mid;
    else lo = mid;
}
return lo;

Rotated Array — Tricky Equal Case

Khi nums[lo] === nums[mid] (với duplicates, e.g., #81): Không thể determine which half is sorted → must lo++ và try again.

Overflow in Mid Calculation 

// WRONG (overflow khi lo + hi > 2^31 - 1):
const mid = (lo + hi) / 2;
 
// CORRECT:
const mid = lo + Math.floor((hi - lo) / 2);

JavaScript numbers are 64-bit float (safe up to 2^53), nhưng good habit anyway.

7. Pattern Recognition

Khi Nào Dùng Binary Search on Answer

“Minimize the MAXIMUM” → Binary search on max value → “Minimize largest sum”, “minimize maximum distance” → check(mid): can we achieve max ≤ mid?

“Maximize the MINIMUM” → Binary search on min value → “Maximize minimum distance”, “maximize minimum pages” → check(mid): can we achieve min ≥ mid?

“K-th smallest in sorted structure” → Binary search on value → check(mid): are there ≥ k elements ≤ mid?

“Feasibility with monotonic threshold” → Binary search on threshold → “At least X bananas/hour”, “ship within D days” → Any problem where check function has monotonic property

“Search in modified sorted array” → Modified binary search → Rotated sorted array, bitonic array, search in 2D matrix

Dấu hiệu nhận biết trong đề bài:

  • “minimum X such that Y is possible”
  • “maximum X such that Z holds”
  • “find kth smallest/largest”
  • “capacity/speed/days optimization”

8. Top LeetCode Problems

#ProblemDifficultyKey Idea
LC-875 #875Koko Eating BananasMediumBS on speed
LC-1011 #1011Capacity to Ship PackagesMediumBS on capacity
LC-410 #410Split Array Largest SumHardBS on max sum
LC-378 #378Kth Smallest Element in MatrixMediumBS on value
LC-33 #33Search in Rotated Sorted ArrayMediumModified BS
LC-81 #81Search in Rotated Array IIMediumHandle duplicates
LC-1482 #1482Minimum Number of Days to Make BouquetsMediumBS on days
LC-1231 #1231Divide ChocolateHardMaximize minimum

Complete Solution: #410 Split Array Largest Sum

// LeetCode #410 — Split Array Largest Sum
// Problem: Split array into m non-empty subarrays to MINIMIZE the largest subarray sum.
// Input: nums = [7,2,5,10,8], m = 2
// Output: 18
// (Split into [7,2,5] and [10,8] → max sum = 18; optimal)
 
function splitArray(nums: number[], m: number): number {
    // ── Define the search space ────────────────────────────────────────────────
    // lo: if we could split into nums.length parts, each part is one element
    //     → minimum possible max = max(nums)  (can't make any part smaller than its element)
    // hi: if we use 1 part (no split), max = sum(nums)
    const lo = Math.max(...nums);
    const hi = nums.reduce((a, b) => a + b, 0);
 
    // ── check(maxSum): Can we split into AT MOST m parts with each sum ≤ maxSum? ──
    // Greedy: greedily extend current subarray until adding next would exceed maxSum.
    // Then start a new part. Count total parts needed.
    const canSplit = (maxSum: number): boolean => {
        let parts = 1;          // always at least 1 part
        let currentSum = 0;
 
        for (const num of nums) {
            if (currentSum + num > maxSum) {
                // Can't add num to current part → start a new part
                parts++;
                currentSum = num;
 
                if (parts > m) return false;    // too many parts needed
            } else {
                currentSum += num;
            }
        }
 
        return true;    // can split into ≤ m parts with max sum ≤ maxSum
    };
 
    // ── Binary search: find smallest maxSum where canSplit is true ────────────
    return binarySearchTemplate(lo, hi, canSplit);
}
 
/*
TRACE for nums = [7,2,5,10,8], m = 2:
 
lo = max(7,2,5,10,8) = 10
hi = 7+2+5+10+8 = 32
 
Iteration 1: mid = 10 + floor((32-10)/2) = 21
  canSplit(21):
    num=7:  currentSum=7
    num=2:  currentSum=9
    num=5:  currentSum=14
    num=10: currentSum=24 > 21 → parts=2, currentSum=10
    num=8:  currentSum=18 ≤ 21 ✓
    parts=2 ≤ m=2 → true
  → hi = 21
 
Iteration 2: mid = 10 + floor((21-10)/2) = 15
  canSplit(15):
    num=7:  currentSum=7
    num=2:  currentSum=9
    num=5:  currentSum=14
    num=10: 14+10=24 > 15 → parts=2, currentSum=10
    num=8:  10+8=18 > 15 → parts=3 > m=2 → false
  → lo = 16
 
Iteration 3: mid = 16 + floor((21-16)/2) = 18
  canSplit(18):
    num=7:  currentSum=7
    num=2:  currentSum=9
    num=5:  currentSum=14
    num=10: 14+10=24 > 18 → parts=2, currentSum=10
    num=8:  10+8=18 ≤ 18 ✓
    parts=2 ≤ m=2 → true
  → hi = 18
 
Iteration 4: mid = 16 + floor((18-16)/2) = 17
  canSplit(17):
    num=7:  currentSum=7
    num=2:  currentSum=9
    num=5:  currentSum=14
    num=10: 14+10=24 > 17 → parts=2, currentSum=10
    num=8:  10+8=18 > 17 → parts=3 > m=2 → false
  → lo = 18
 
lo=18, hi=18 → STOP, return 18 ✓
 
WHY GREEDY WORKS for canSplit:
- We want minimum number of parts for a given maxSum.
- Greedy (extend as far as possible) is optimal because:
  Making a part shorter never helps — it only creates more parts elsewhere.
  Proof: if any split uses ≤ m parts, greedy also uses ≤ m parts.
 
Time:  O(N log S) — S = sum(nums), log S binary search iterations, each O(N) check
Space: O(1) — only constant extra space
*/

9. Self-Assessment Checklist

Checklist sau khi học Advanced Binary Search

  • Giải thích được “binary search on the answer” concept với ví dụ cụ thể
  • Implement universal template với lo/hi/check function
  • Biết khi nào dùng hi = mid vs hi = mid - 1 (minimize vs maximize)
  • Biết tại sao maximize variant cần Math.ceil cho mid
  • Giải #875 Koko Eating Bananas không nhìn note
  • Giải #410 Split Array Largest Sum và giải thích greedy check
  • Search in Rotated Sorted Array — xác định đúng half nào sorted
  • Nhận ra “binary search on answer” pattern khi đọc đề bài mới
  • Chứng minh được tại sao predicate trong một bài cụ thể là monotonic

Luyện tập tiếp theo

  • #1231 Divide Chocolate (maximize minimum)
  • #774 Minimize Max Distance to Gas Station
  • #1552 Magnetic Force Between Two Balls
  • #2064 Minimized Maximum of Products Distributed to Any Store
  • Kth problems: #719 Find K-th Smallest Pair Distance

Tags: dsa binary-search parametric-search binary-search-on-answer faang-mastery Related: 03-Monotonic-Stack-Queue | 05-Divide-and-Conquer | Pattern-Binary-Search

Graph View

Backlinks