Buổi 05 — Binary Search

Navigation

← 04-Recursion-and-Backtracking | → 06-Sorting-Merge-Quick Giai đoạn: Big Tech Foundation | Độ khó: ⭐⭐⭐

1. Analogy & Context

Trò chơi đoán số

Bạn đoán một số từ 1 đến 100. Người chơi thông minh luôn đoán số ở giữa — 50. Nếu sai, họ biết ngay phải tìm ở nửa nào, và lại đoán giữa của nửa đó.

Kết quả? 100 số → tối đa 7 lần đoán. 1 tỷ số → tối đa 30 lần đoán.

Đây chính xác là Binary Search — mỗi bước loại bỏ một nửa không gian tìm kiếm còn lại.

Lần đoán 1: [1 ........... 50 ........... 100]  → đoán 50
Lần đoán 2: [1 ...... 25 ...... 50]               → đoán 25
Lần đoán 3: [25 .. 37 .. 50]                       → đoán 37
...
Chỉ cần log₂(100) ≈ 7 lần

Tại sao Binary Search quan trọng?

Sequential search (linear): $O (N)$ — duyệt từng phần tử
Binary search: $O (lo g N)$ — với $N = 1 0^{9}$ , chỉ cần ~30 bước
Điều kiện tiên quyết: mảng đã được sắp xếp (hoặc không gian tìm kiếm có tính monotonic)

Monotonic = Chìa khóa của Binary Search

Binary search hoạt động khi không gian tìm kiếm có tính chất: một khi điều kiện f(x) đúng, thì f(x+1) cũng đúng (hoặc ngược lại). Tính “monotonic” không chỉ giới hạn ở mảng đã sort!

2. The FAANG Standard

Hai kỹ thuật phải thành "muscle memory"

Classic binary search — tìm exact match

Lower bound / Upper bound — tìm biên giới của target trong mảng có duplicates

Binary search on the answer — kỹ thuật cấp FAANG, disguised hard problems

“Binary search on the answer” là gì?

Thay vì tìm kiếm trên mảng dữ liệu, ta binary search trên miền kết quả:

“Tốc độ ăn chuối tối thiểu để ăn xong trong H giờ” → binary search trên speed từ 1 → max
“Số ngày tối thiểu để ship tất cả packages” → binary search trên capacity
Bất cứ bài toán dạng “minimize the maximum” hay “maximize the minimum”

Dấu hiệu nhận biết "Binary Search on the Answer"

Đề hỏi “minimum X sao cho điều kiện thỏa mãn”

Đề hỏi “maximum X sao cho điều kiện thỏa mãn”

Constraint lớn: $N \leq 1 0^{9}$ → gợi ý $O (lo g N)$ solution

3. Visual Thinking (Mermaid)

3.1 Classic Binary Search — Step by Step

graph TD
    A["arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]<br/>target = 23"] --> B

    B["left=0, right=9<br/>mid = 4, arr[4]=16<br/>16 < 23 → move left pointer"] --> C

    C["left=5, right=9<br/>mid = 7, arr[7]=56<br/>56 > 23 → move right pointer"] --> D

    D["left=5, right=6<br/>mid = 5, arr[5]=23<br/>23 == 23 → FOUND at index 5"] --> E["return 5 ✓"]

    style A fill:#1e3a5f,color:#fff
    style E fill:#1a4731,color:#fff

3.2 Lower Bound vs Upper Bound

graph LR
    subgraph arr["arr = [1, 2, 2, 2, 3, 4] — target = 2"]
        direction LR
        A0["1"] --> A1["2"] --> A2["2"] --> A3["2"] --> A4["3"] --> A5["4"]
    end

    subgraph LB["lowerBound — first index where arr[i] >= target"]
        B1["Khi arr[mid] >= target → right = mid (không loại mid)"]
        B2["Khi arr[mid] < target → left = mid + 1"]
        B3["Kết quả: index 1 (phần tử 2 đầu tiên)"]
    end

    subgraph UB["upperBound — first index where arr[i] > target"]
        C1["Khi arr[mid] > target → right = mid"]
        C2["Khi arr[mid] <= target → left = mid + 1"]
        C3["Kết quả: index 4 (sau phần tử 2 cuối cùng)"]
    end

3.3 Binary Search on Answer — “Minimize the Maximum”

graph TD
    A["Bài toán: Tìm tốc độ ăn tối thiểu (Koko #875)"] --> B
    B["Xác định search space:<br/>lo = 1 (tốc độ tối thiểu)<br/>hi = max(piles) (tốc độ tối đa)"] --> C
    C["mid = (lo + hi) / 2<br/>Kiểm tra: có thể ăn hết trong H giờ không?"] --> D
    D{canFinish?}
    D -->|YES| E["hi = mid<br/>(thử tốc độ thấp hơn)"]
    D -->|NO| F["lo = mid + 1<br/>(cần nhanh hơn)"]
    E --> G{lo < hi?}
    F --> G
    G -->|YES| C
    G -->|NO| H["return lo — tốc độ tối thiểu ✓"]

    style H fill:#1a4731,color:#fff

4. TypeScript Template

4.1 Classic Binary Search — Exact Match

/**
 * Binary Search — tìm exact match trong sorted array
 * Time: O(log N) | Space: O(1)
 *
 * LeetCode #704
 */
function binarySearch(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;
 
    while (left <= right) {
        // QUAN TRỌNG: Dùng left + (right - left) / 2 thay vì (left + right) / 2
        // Lý do: (left + right) có thể overflow nếu left, right là số 32-bit lớn
        // Ví dụ: left = 2^30, right = 2^30 + 1 → left + right = 2^31 + 1 > MAX_INT
        // left + (right - left) / 2 luôn an toàn vì (right - left) luôn >= 0
        const mid = left + Math.floor((right - left) / 2);
 
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;  // target ở bên phải mid
        } else {
            right = mid - 1; // target ở bên trái mid
        }
    }
 
    return -1; // không tìm thấy
}

4.2 Lower Bound — First Index Where arr[i] >= target

/**
 * Lower Bound — tìm index đầu tiên mà arr[i] >= target
 * Nếu target không tồn tại, trả về vị trí chèn vào để mảng vẫn sorted
 *
 * Trick: loop bất biến là: arr[right] >= target (nếu tồn tại)
 * → dùng left < right (không phải <=) vì right có thể là câu trả lời
 */
function lowerBound(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length; // right = length (không phải length-1) để handle "chèn cuối"
 
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
 
        if (arr[mid] >= target) {
            right = mid;     // mid có thể là answer, giữ lại
        } else {
            left = mid + 1;  // mid chắc chắn không phải answer
        }
    }
 
    return left; // left === right tại điểm dừng
}

4.3 Upper Bound — First Index Where arr[i] > target

/**
 * Upper Bound — tìm index đầu tiên mà arr[i] > target
 * Số phần tử bằng target = upperBound(target) - lowerBound(target)
 */
function upperBound(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length;
 
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
 
        if (arr[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
 
    return left;
}
 
// Usage example:
// arr = [1, 2, 2, 2, 3, 4]
// lowerBound(arr, 2) → 1  (index đầu tiên của 2)
// upperBound(arr, 2) → 4  (index sau 2 cuối cùng)
// count of 2s = 4 - 1 = 3 ✓

4.4 Search a 2D Matrix — LeetCode #74

/**
 * LeetCode #74 — Search a 2D Matrix
 * Ma trận m×n: mỗi hàng sorted, hàng đầu của hàng i+1 > hàng cuối hàng i
 *
 * Key insight: Treat the 2D matrix as a 1D sorted array of size m*n
 * Index mapping: index → row = Math.floor(index / n), col = index % n
 *
 * Time: O(log(m*n)) | Space: O(1)
 */
function searchMatrix(matrix: number[][], target: number): boolean {
    const m = matrix.length;
    const n = matrix[0].length;
 
    let left = 0;
    let right = m * n - 1;
 
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
 
        // Convert 1D index → 2D coordinates
        const row = Math.floor(mid / n);
        const col = mid % n;
        const val = matrix[row][col];
 
        if (val === target) return true;
        if (val < target) left = mid + 1;
        else right = mid - 1;
    }
 
    return false;
}

4.5 Find Peak Element — Binary Search on Unsorted

/**
 * LeetCode #162 — Find Peak Element
 * Mảng KHÔNG sorted nhưng vẫn dùng binary search được!
 *
 * Key insight: Nếu arr[mid] < arr[mid+1], thì peak nằm ở bên phải
 * Lý do: slope đang đi lên → đỉnh phải ở đâu đó bên phải
 * (Ngay cả khi tiếp tục đi xuống sau đó, arr[-1] = arr[n] = -infinity đảm bảo có peak)
 *
 * Time: O(log N) | Space: O(1)
 */
function findPeakElement(nums: number[]): number {
    let left = 0;
    let right = nums.length - 1;
 
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
 
        if (nums[mid] < nums[mid + 1]) {
            // Đang đi lên → peak ở bên phải
            left = mid + 1;
        } else {
            // Đang đi xuống (hoặc nums[mid] > nums[mid+1]) → peak ở bên trái hoặc tại mid
            right = mid;
        }
    }
 
    return left;
}

4.6 Koko Eating Bananas — Binary Search on Answer (LeetCode #875)

/**
 * LeetCode #875 — Koko Eating Bananas
 *
 * Bài toán: Koko có piles[i] chuối ở đống i. H giờ. Mỗi giờ ăn speed k.
 * Tìm k tối thiểu để ăn hết tất cả trong H giờ.
 *
 * Pattern: Binary Search on Answer
 * - Search space: k từ 1 đến max(piles)
 * - Predicate: canFinish(k) = tổng thời gian ăn với speed k <= H
 * - Tính monotonic: nếu canFinish(k) = true thì canFinish(k+1) = true
 *   → Tìm k nhỏ nhất mà canFinish(k) = true → LOWER BOUND pattern
 *
 * Time: O(N log M) — N = số đống, M = max(piles)
 * Space: O(1)
 */
function minEatingSpeed(piles: number[], h: number): number {
    // Xác định search space
    let lo = 1;                          // tốc độ thấp nhất có thể
    let hi = Math.max(...piles);         // tốc độ cao nhất cần thiết (1 giờ = 1 đống)
 
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
 
        if (canFinish(piles, mid, h)) {
            hi = mid;       // mid có thể là answer, thử thấp hơn
        } else {
            lo = mid + 1;   // mid quá chậm, cần nhanh hơn
        }
    }
 
    return lo;
}
 
/**
 * Kiểm tra: với speed k, có ăn hết trong h giờ không?
 * Math.ceil(pile / k) = số giờ cần cho đống pile khi tốc độ k
 */
function canFinish(piles: number[], k: number, h: number): boolean {
    let hours = 0;
    for (const pile of piles) {
        hours += Math.ceil(pile / k);
    }
    return hours <= h;
}
 
/*
 * Walkthrough với piles = [3, 6, 7, 11], h = 8:
 *
 * lo=1, hi=11 → mid=6
 *   canFinish(6)? ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6) = 1+1+2+2 = 6 <= 8 → YES
 *   hi = 6
 *
 * lo=1, hi=6 → mid=3
 *   canFinish(3)? ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3) = 1+2+3+4 = 10 > 8 → NO
 *   lo = 4
 *
 * lo=4, hi=6 → mid=5
 *   canFinish(5)? ceil(3/5)+ceil(6/5)+ceil(7/5)+ceil(11/5) = 1+2+2+3 = 8 <= 8 → YES
 *   hi = 5
 *
 * lo=4, hi=5 → mid=4
 *   canFinish(4)? ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 <= 8 → YES
 *   hi = 4
 *
 * lo=4, hi=4 → DONE, return 4 ✓
 */

5. Complexity Deep-dive

Tại sao O(log N)?

Mỗi iteration, ta giảm search space xuống một nửa:

$N \to \frac{N}{2} \to \frac{N}{4} \to \frac{N}{8} \to \dots \to 1$

Sau $k$ bước: $\frac{N}{2 ^{k}} = 1 \Rightarrow k = lo g_{2} N$

log₂(10⁹) ≈ 30 — Con số “thần kỳ”

N	log₂(N)	Ý nghĩa
$1 0^{3}$	~10	1,000 phần tử → 10 bước
$1 0^{6}$	~20	1 triệu → 20 bước
$1 0^{9}$	~30	1 tỷ → 30 bước
$1 0^{18}$	~60	max long → 60 bước

Tại sao điều này quan trọng

Khi đề bài có constraint $1 \leq answer \leq 1 0^{9}$ , binary search on answer chỉ cần ~30 iteration. Với mỗi iteration là $O (N)$ check, tổng là $O (N lo g M)$ — hoàn toàn khả thi.

Space Complexity

Iterative binary search: $O (1)$ — chỉ cần 3 biến left, right, mid
Recursive binary search: $O (lo g N)$ — call stack depth

Luôn dùng iterative khi có thể

Iterative tốt hơn recursive cho binary search: tiết kiệm stack space, tránh stack overflow với $N$ lớn.

6. Edge Cases & Pitfalls

Pitfall #1 — Infinite Loop khi left = right - 1

// SAI — có thể infinite loop
while (left < right) {
    const mid = Math.floor((left + right) / 2); // mid = left khi right = left + 1
    if (condition) {
        left = mid; // left không thay đổi! → infinite loop
    }
}
 
// ĐÚNG — đảm bảo progress
while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (condition) {
        right = mid;   // hoặc left = mid + 1
    } else {
        left = mid + 1; // luôn có progress
    }
}

Pitfall #2 — Integer Overflow

// SAI — có thể overflow (dù TypeScript/JS dùng float64, vẫn nên có thói quen tốt)
const mid = Math.floor((left + right) / 2);
 
// ĐÚNG — không bao giờ overflow
const mid = left + Math.floor((right - left) / 2);
// Vì right - left luôn >= 0, và left + (something >= 0) luôn hợp lệ

Pitfall #3 — Off-by-one: left < right vs left ⇐ right

// Dùng left <= right khi: tìm exact match, right = arr.length - 1
// → loop kết thúc khi không còn phần tử nào để xét
 
// Dùng left < right khi: tìm lower/upper bound, right = arr.length
// → loop kết thúc khi left = right, đây là câu trả lời
 
// Rule of thumb:
// - Exact match → left <= right, return -1 nếu không tìm thấy
// - Bound finding → left < right, return left (= right)

Pitfall #4 — Returning Wrong Boundary

// Sau khi loop kết thúc với left = right:
// - lowerBound: return left (vị trí phần tử đầu tiên >= target)
// - upperBound: return left (vị trí phần tử đầu tiên > target)
// - Exact match với left > right: return -1
 
// Thường gặp: return left-1 thay vì left → sai 1 đơn vị

Pitfall #5 — Mảng có duplicates

const arr = [1, 2, 2, 2, 3];
 
// Classic binary search có thể return index 2 (giữa) — không deterministic
// Nếu cần index đầu tiên của 2 → dùng lowerBound → trả về 1
// Nếu cần index cuối cùng của 2 → dùng upperBound(2) - 1 → trả về 3
// Nếu chỉ cần biết có tồn tại → classic binary search đủ

7. Pattern Recognition

Từ khóa nhận dạng Binary Search

Trên mảng dữ liệu:

“Sorted array” + “find / search” → Classic binary search
“Find first / last occurrence” → Lower bound / Upper bound
“Search in rotated sorted array” → Binary search với điều kiện phức tạp hơn
“Find peak element” → Binary search dựa trên slope (không cần sorted)
“Kth smallest in sorted matrix” → Binary search on answer + count

Binary Search on Answer:

“Minimum speed / capacity / days such that …”
“Maximize the minimum” / “Minimize the maximum”
“Can we achieve X? Find minimum X”
Constraint có dạng: answer nằm trong range lớn $[1, 1 0^{9}]$

Template nhận dạng:

Nếu đề hỏi: "Tìm minimum k sao cho f(k) = true"
và f có tính: f(k) = true → f(k+1) = true (monotonic)
→ Binary search on [lo, hi] tìm lower bound của f(k) = true

8. Top LeetCode Problems

#	Tên	Độ khó	Pattern	Ghi chú
LC-704 #704	Binary Search	Easy	Classic	Bài căn bản nhất
LC-35 #35	Search Insert Position	Easy	Lower Bound	lowerBound application
LC-74 #74	Search a 2D Matrix	Medium	2D → 1D mapping	Index conversion trick
LC-33 #33	Search in Rotated Sorted Array	Medium	Modified BS	Xác định nửa nào sorted
LC-875 #875	Koko Eating Bananas	Medium	BS on Answer	Template chuẩn cho dạng này
LC-162 #162	Find Peak Element	Medium	Slope-based BS	Không cần mảng sorted
LC-410 #410	Split Array Largest Sum	Hard	BS on Answer	Minimize the maximum

Lộ trình học

#704 → nắm vững template cơ bản

#35 → hiểu lower bound

#875 → master “BS on answer” pattern

#33 → binary search với logic phức tạp hơn

#410 → hard-level BS on answer

9. Self-Assessment Checklist

Kiểm tra mức độ thành thạo

Level 1 — Cơ bản:

Viết được classic binary search từ đầu, không nhìn tài liệu
Giải thích được tại sao dùng left + (right - left) / 2
Biết khi nào dùng left <= right vs left < right
Xác định được sau loop, return left hay right hay left-1

Level 2 — Intermediate:

Implement được lowerBound và upperBound chính xác
Giải được #74 (2D matrix) bằng index mapping
Nhận ra được “BS on answer” pattern khi đọc đề
Implement được #875 (Koko) với đúng lo/hi/predicate

Level 3 — FAANG-ready:

Giải được #33 (rotated array) — xác định nửa sorted
Giải được #410 (split array) — hard-level BS on answer
Tự tạo predicate function cho bài toán mới từ scratch
Giải thích được tại sao $lo g_{2} (1 0^{9}) \approx 30$ và ý nghĩa với constraint

Thực hành hiệu quả

Sau mỗi bài binary search, tự hỏi:

Search space của mình là gì? [lo, hi] = ?

Predicate f(x) là gì? Khi nào true, khi nào false?

Mình tìm lower bound hay upper bound của f(x)?

Boundary update: hi = mid hay lo = mid + 1?

Tags: binary-search algorithms FAANG searching two-pointers-adjacent Liên kết: 04-Recursion-and-Backtracking | 06-Sorting-Merge-Quick | Pattern-Binary-Search-on-Answer

lthieu's notes

Explorer

05-Binary-Search

Buổi 05 — Binary Search

1. Analogy & Context

2. The FAANG Standard

3. Visual Thinking (Mermaid)

3.1 Classic Binary Search — Step by Step

3.2 Lower Bound vs Upper Bound

3.3 Binary Search on Answer — “Minimize the Maximum”

4. TypeScript Template

4.1 Classic Binary Search — Exact Match

4.2 Lower Bound — First Index Where arr[i] >= target

4.3 Upper Bound — First Index Where arr[i] > target

4.4 Search a 2D Matrix — LeetCode #74

4.5 Find Peak Element — Binary Search on Unsorted

4.6 Koko Eating Bananas — Binary Search on Answer (LeetCode #875)

5. Complexity Deep-dive

Tại sao O(log N)?

log₂(10⁹) ≈ 30 — Con số “thần kỳ”

Space Complexity

6. Edge Cases & Pitfalls

7. Pattern Recognition

8. Top LeetCode Problems

9. Self-Assessment Checklist

Graph View

Table of Contents

Backlinks