1.1 Binary Search là gì?

Hai điều kiện phải có để áp dụng

1. Không gian có thứ tự — array đã sort, hoặc một thuộc tính monoton trên answer space.
2. Hàm kiểm tra (predicate) trả True/False, và là monoton: F → F → ... → T → T → ... Tìm boundary giữa F và T là mục tiêu.

Vì sao mạnh?

Với n = 10⁹, O(log n) = 30 bước. Đây là khác biệt giữa "1 giây" và "10 năm". Nhiều bài có n ≤ 10⁹ bắt buộc phải dùng Binary Search hoặc công thức toán.

1.2 Template chuẩn — Half-open [left, right)

Có rất nhiều phiên bản Binary Search. Khoá học này dùng 1 template duy nhất để tránh nhầm:

def binary_search(arr, target):
    left, right = 0, len(arr)         # half-open: right không truy cập
    while left < right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return -1

Vì sao chọn half-open?

• right = len(arr) ban đầu — không có "off-by-one" với index cuối.
• Điều kiện left < right — vùng rỗng khi left == right.
• left = mid + 1 và right = mid — không bao giờ kẹt vô tận.
• Khi thoát, left == right = vị trí "lower bound" của target.

Template này dùng được cho cả "tìm chính xác" và "tìm boundary" — chỉ thay đổi điều kiện so sánh.

1.3 Lower bound vs Upper bound

Hai biến thể quan trọng của BS — phải phân biệt rõ:

Lower bound — vị trí đầu tiên mà arr[i] ≥ target

def lower_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

Upper bound — vị trí đầu tiên mà arr[i] > target

def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left

Khác biệt: so sánh với ≤ hay <.

1.4 Bốn bẫy kinh điển

1. Vòng lặp vô tận.

   # SAI — kẹt khi left = mid:
   while left < right:
       mid = (left + right) // 2
       if condition: left = mid          # mid không đổi!
   # ĐÚNG: left = mid + 1

2. Tràn số khi tính mid. Trong C++/Java, (left + right) / 2 tràn nếu cả hai gần INT_MAX. Dùng left + (right − left) // 2. Python không có vấn đề này nhưng nên viết theo thói quen.
3. Nhầm left ≤ right với left < right. Hai loại template tồn tại; trộn chúng dẫn đến bug. Khuyên dùng nhất quán half-open.
4. Nghĩ rằng BS chỉ chạy trên array. BS chạy trên mọi không gian có thứ tự với predicate monoton. Đây là ý tưởng then chốt cho Phần 4.

2.1 Worked Example 1 — Classic Binary Search

Đề (LeetCode #704): Mảng nums sort tăng. Tìm index của target, -1 nếu không có.

def search(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return -1

Trace với nums = [-1, 0, 3, 5, 9, 12], target = 9

Time O(log n), Space O(1).

2.2 Worked Example 2 — Find First and Last Position

Đề (LeetCode #34): Mảng sort. Tìm index đầu và cuối của target. Trả [-1, -1] nếu không có. Yêu cầu O(log n).

Dùng lower_bound + upper_bound

def searchRange(nums, target):
    def lower(t):
        l, r = 0, len(nums)
        while l < r:
            m = (l + r) // 2
            if nums[m] < t: l = m + 1
            else: r = m
        return l

    first = lower(target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    last = lower(target + 1) - 1     # mẹo: upper bound = lower(target+1)
    return [first, last]

Time O(log n), Space O(1).

2.3 First and Last Position — Trace

nums = [5,7,7,8,8,10], target = 8. Kỳ vọng: [3, 4].

lower(8)

lower(9) − 1 = upper bound của 8 trừ 1

Tương tự, lower(9) = 5 → last = 4.

Kết quả: [3, 4]. Time O(log n).

2.4 Worked Example 3 — Search Insert Position

Đề (LeetCode #35): Mảng sort, target. Trả về index nơi target nên được chèn vào.

Đây chính là lower_bound — vị trí đầu tiên ≥ target.

def searchInsert(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

Time O(log n), Space O(1).

2.5 Worked Example 4 — Sqrt(x) bằng Binary Search

Đề (LeetCode #69): Cho số nguyên không âm x. Trả floor(sqrt(x)). Không dùng built-in sqrt.

BS trên answer space [0, x]

Đây là bài đầu tiên minh hoạ "BS không nhất thiết trên array". Tìm số r lớn nhất sao cho r² ≤ x.

def mySqrt(x):
    if x < 2: return x
    left, right = 1, x
    while left < right:
        mid = (left + right + 1) // 2     # ceil — tìm cận trên
        if mid * mid <= x:
            left = mid
        else:
            right = mid - 1
    return left

Time O(log x), Space O(1).

Knowledge Check — BS trên Array

3.1 Rotated Sorted Array — Trực giác

Rotated = mảng sort nhưng bị "cắt và ghép" tại điểm pivot. Ví dụ: [4,5,6,7,0,1,2] là [0,1,2,4,5,6,7] rotated tại pivot 4.

Quan sát then chốt

Với mid bất kỳ, một trong hai nửa luôn còn sort: nửa trái [l..mid] hoặc nửa phải [mid..r].

Quy trình: kiểm tra nửa nào sort → nếu target nằm trong khoảng sort đó, BS bên đó; ngược lại bên kia.

3.2 Worked Example 5 — Search in Rotated Sorted Array

Đề (LeetCode #33): Mảng đã rotate. Tìm target. O(log n).

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        # Xác định nửa nào sort
        if nums[left] <= nums[mid]:                   # nửa trái sort
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:                                         # nửa phải sort
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Time O(log n), Space O(1).

3.3 Search Rotated — Trace

nums = [4,5,6,7,0,1,2], target = 0. Kỳ vọng: 4.

3 bước log₂(7) ≈ 3 — đúng O(log n).

3.4 Worked Example 6 — Find Minimum in Rotated Sorted Array

Đề (LeetCode #153): Mảng đã rotate, không trùng. Tìm phần tử nhỏ nhất.

Quan sát

Min nằm ở "vết cắt" — vị trí mà nums[i] < nums[i-1]. So sánh nums[mid] với nums[right]:

• Nếu nums[mid] > nums[right]: vết cắt ở bên phải mid → left = mid + 1.
• Ngược lại: vết cắt ở bên trái hoặc tại mid → right = mid.

def findMin(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

Time O(log n).

3.5 Worked Example 7 — Find Peak Element

Đề (LeetCode #162): Mảng nums. Một "peak" là nums[i] > nums[i-1] và nums[i] > nums[i+1]. Trả về index của một peak bất kỳ. Giả sử nums[-1] = nums[n] = -∞. Yêu cầu O(log n).

Trực giác

Mảng không cần sort. Nhưng vẫn áp dụng BS được vì có "monotonicity" cục bộ: nếu nums[mid] < nums[mid+1], bên phải chắc chắn có peak (vì hàm đang đi lên và phải xuống lại sau hữu hạn bước).

def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1                # peak bên phải
        else:
            right = mid                   # peak bên trái hoặc tại mid
    return left

Time O(log n).

Knowledge Check — BS trên Rotated

4.1 Pattern: Parametric Binary Search

Tín hiệu nhận biết

• Đề có "minimum X such that...", "maximum X such that...".
• Phạm vi của X có thể rất lớn (10⁹ trở lên).
• Hàm kiểm tra canDo(X) dễ viết và chạy nhanh (thường O(n) hoặc O(n log n)).

Khi cả ba có → BS trên answer space.

4.2 Template Parametric BS

def parametric_bs(low, high, can_do):
    """Tìm X nhỏ nhất sao cho can_do(X) == True."""
    while low < high:
        mid = (low + high) // 2
        if can_do(mid):
            high = mid                # mid khả thi → cố nhỏ hơn
        else:
            low = mid + 1             # mid không khả thi → phải lớn hơn
    return low

Quy trình thiết kế

1. Xác định biên answer space: low = giá trị nhỏ nhất khả dĩ; high = giá trị lớn nhất.
2. Viết hàm can_do(X): cho X này, có làm được không? Kiểm tra monoton (vẽ trên giấy: với X tăng thì can_do từ False/True đến True/True).
3. Áp dụng template.

4.3 Worked Example 8 — Koko Eating Bananas

Đề (LeetCode #875): Koko có piles[i] chuối ở đống thứ i. Mỗi giờ ăn k quả từ một đống (nếu đống < k, chỉ ăn hết đống). Bảo vệ về sau h giờ. Tìm k nhỏ nhất để ăn hết trước khi bảo vệ về.

Phân tích

• Answer space: k ∈ [1, max(piles)] — không cần lớn hơn max.
• can_do(k): tổng giờ với tốc độ k = sum(ceil(p / k) for p in piles); can_do = (total ≤ h).
• Monotonicity: k tăng → tổng giờ giảm. Predicate from F → F → ... → T → T → ...

import math
def minEatingSpeed(piles, h):
    def can_do(k):
        return sum(math.ceil(p / k) for p in piles) <= h

    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_do(mid):
            high = mid
        else:
            low = mid + 1
    return low

Time O(n log(max(piles))).

4.4 Koko — Trace

piles = [3, 6, 7, 11], h = 8. Kỳ vọng: 4.

Answer space: [1, 11].

Kết quả: k = 4. Chỉ tốn ~log₂(11) ≈ 4 lần can_do call.

4.5 Worked Example 9 — Capacity to Ship Packages Within D Days

Đề (LeetCode #1011): Mảng weights, số ngày days. Tàu phải chở hàng theo thứ tự, mỗi ngày chở liên tiếp. Tìm capacity nhỏ nhất.

Phân tích

• Answer space: cap ∈ [max(weights), sum(weights)]. Cận dưới phải ≥ max(weights) (kẻo không chở được 1 món); cận trên = sum (chở hết trong 1 ngày).
• can_do(cap): greedy — chia mảng thành đoạn liên tiếp có tổng ≤ cap; can_do = (số đoạn ≤ days).

def shipWithinDays(weights, days):
    def can_do(cap):
        d = 1
        cur = 0
        for w in weights:
            if cur + w > cap:
                d += 1
                cur = 0
            cur += w
        return d <= days

    low, high = max(weights), sum(weights)
    while low < high:
        mid = (low + high) // 2
        if can_do(mid):
            high = mid
        else:
            low = mid + 1
    return low

Time O(n log(sum)).

4.6 Worked Example 10 — Median of Two Sorted Arrays (Hard)

Đề (LeetCode #4, Hard): Hai mảng sort nums1, nums2 tổng size n+m. Tìm median. Yêu cầu O(log(n+m)).

Ý tưởng — BS trên "đường chia"

Đặt i là số phần tử lấy từ nums1 cho nửa trái. Khi đó j = (n+m+1)/2 − i phần tử từ nums2. Cần tìm i sao cho nums1[i-1] ≤ nums2[j] và nums2[j-1] ≤ nums1[i] — đảm bảo nửa trái ≤ nửa phải.

def findMedianSortedArrays(A, B):
    if len(A) > len(B): A, B = B, A         # đảm bảo BS trên array nhỏ
    n, m = len(A), len(B)
    half = (n + m + 1) // 2
    low, high = 0, n
    while low <= high:
        i = (low + high) // 2
        j = half - i
        Aleft  = A[i-1] if i > 0 else float('-inf')
        Aright = A[i]   if i < n else float('inf')
        Bleft  = B[j-1] if j > 0 else float('-inf')
        Bright = B[j]   if j < m else float('inf')
        if Aleft <= Bright and Bleft <= Aright:
            if (n + m) % 2:
                return max(Aleft, Bleft)
            return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
        elif Aleft > Bright:
            high = i - 1
        else:
            low = i + 1

4.7 Median of Two Sorted Arrays — Phân tích

Vì sao BS trên array nhỏ?

Để đảm bảo j = half − i luôn hợp lệ (≥ 0). Nếu n < m, biên của i ∈ [0, n] hẹp hơn ⟹ j ≥ 0 luôn được đảm bảo.

Trực giác đường chia

Hình dung "đường thẳng" chia mảng tổng thành 2 nửa bằng nhau. Đường này đi qua nums1 ở vị trí i và nums2 ở vị trí j. Median sẽ ở chính giữa khi:

Vì sao "+1" trong half?

(n + m + 1) // 2 đảm bảo nửa trái có ≥ nửa phải 0 hoặc 1 phần tử. Khi tổng lẻ, median = max nửa trái. Khi tổng chẵn, median = average của max nửa trái và min nửa phải.

Time O(log min(n, m)). Đây là một trong những bài Hard kinh điển nhất — sinh viên hiểu được = đã làm chủ BS.

Knowledge Check — BS on Answer Space

5.1 Decision Tree — Khi nào dùng Binary Search?

Ba câu hỏi check trước khi code

1. Không gian tìm kiếm là gì? (mảng / answer space / 2D matrix)
2. Predicate monoton như thế nào? (F→T hay T→F?)
3. Biên low/high tighten đến mức nào hợp lý?

Tổng kết Tuần 7

Đã học

• Template chuẩn half-open — một template cho mọi bài, tránh off-by-one.
• Lower/Upper bound — kỹ thuật cốt lõi để đếm và tìm boundary.
• BS trên rotated array — quan sát "luôn có 1 nửa sort"; mở rộng đến Find Peak (monotonicity cục bộ).
• Parametric BS / BS on Answer Space — pattern then chốt cho phỏng vấn senior; biến bài "tối ưu" thành bài "kiểm tra".
• Boss-level: Median of Two Sorted Arrays — BS trên đường chia.
• Tín hiệu mạnh: constraint n ≤ 10⁹ hoặc cụm "min X sao cho có thể Y" → BS.

Bài về nhà (12 bài)

1. LeetCode #704 — Binary Search
2. LeetCode #34 — Find First and Last Position
3. LeetCode #35 — Search Insert Position
4. LeetCode #69 — Sqrt(x)
5. LeetCode #33 — Search in Rotated Sorted Array
6. LeetCode #153 — Find Minimum in Rotated Sorted Array
7. LeetCode #162 — Find Peak Element
8. LeetCode #875 — Koko Eating Bananas
9. LeetCode #1011 — Capacity to Ship Packages Within D Days
10. LeetCode #410 — Split Array Largest Sum (parametric BS)
11. LeetCode #4 — Median of Two Sorted Arrays (Hard)
12. LeetCode #74 — Search a 2D Matrix