Chương 25 - Advanced Binary Search (Search on Answer)

Chương 5 dạy binary search trên mảng đã sort. Chương này dạy kỹ thuật mạnh hơn: binary search trên đáp án (search on answer / parametric search). Khi không gian đáp án có predicate đơn điệu, ta binary search trên giá trị đáp án thay vì index.

Mục tiêu chương

Sau chương này, bạn sẽ:

• Search on answer: predicate check(x) đơn điệu trên giá trị x.
• Bound chuẩn: lo = min possible, hi = max possible.
• Phân biệt “first True” vs “last True” (ceil mid khác floor mid).
• Pattern khác: Median of Two Sorted Arrays - binary partition, không phải search on answer.

Khi nào dùng pattern này?

• Bài hỏi “min X sao cho …” hoặc “max X sao cho …” - và bạn nhận diện được predicate check(X) đơn điệu.
• Khi range đáp án có thể bound trên/dưới rõ ràng.
• Dấu hiệu: “tìm số nhỏ nhất / lớn nhất thoả mãn” + bài có vẻ DP nhưng state cồng kềnh.

Quy trình: 1. Xác định đáp án là biến gì (capacity, speed, distance, …). 2. Bound [lo, hi] của đáp án. 3. Viết check(mid) -> bool đơn điệu. 4. Binary search “first True” hoặc “last True”.

Template code

def search_on_answer(lo: int, hi: int, check) -> int:
    """Tìm giá trị nhỏ nhất trong [lo, hi] thoả check(x)=True."""
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid                # cố thu nhỏ về True
        else:
            lo = mid + 1
    return lo

Bài tự luyện cuối chương

• LC 668 - Kth Smallest Number in Multiplication Table
• LC 1283 - Find the Smallest Divisor Given a Threshold
• LC 1482 - Minimum Number of Days to Make m Bouquets
• LC 2616 - Minimize the Maximum Difference of Pairs

---

25.1 Koko Eating Bananas (LC 875)

Đề bài

Koko có n đống chuối, đống i có piles[i] quả. Mỗi giờ Koko ăn 1 đống với tốc độ k quả/giờ (nếu đống < k, vẫn coi như 1 giờ). Tìm k nhỏ nhất để ăn hết trong h giờ.

Ví dụ

Input:  piles = [3,6,7,11], h = 8   → 4
Input:  piles = [30,11,23,4,20], h = 5 → 30
Input:  piles = [30,11,23,4,20], h = 6 → 23

Ràng buộc

• 1 <= len(piles) <= 10^4
• piles.length <= h <= 10^9
• 1 <= piles[i] <= 10^9

Clarifying questions

• h ≥ len(piles)? → Đảm bảo theo đề.
• Một đống đã rất lớn? → k vẫn ≤ max(piles).

Hướng tiếp cận

Đáp án k ∈ [1, max(piles)]. Predicate check(k) = “ăn hết trong ≤ h giờ?”.

time(k) = Σ ceil(piles[i] / k). Predicate đơn điệu: k lớn hơn → time nhỏ hơn. → Tìm k nhỏ nhất thoả time(k) ≤ h.

Code Python 3

from math import ceil
from typing import List

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def can_finish(k: int) -> bool:
            return sum((p + k - 1) // k for p in piles) <= h

        lo, hi = 1, max(piles)
        while lo < hi:
            mid = (lo + hi) // 2
            if can_finish(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

Phân tích độ phức tạp

• Thời gian: O(n log(max_pile)). Bộ nhớ: O(1).

Bình luận

• Ceil division (p + k - 1) // k tránh dùng math.ceil với float.
• Pattern “search on answer” rõ ràng ở đây: predicate đơn điệu giảm với k tăng.

Bài tự luyện liên quan

• LC 1011 - Capacity To Ship Packages (bài 25.2).
• LC 1283 - Find the Smallest Divisor.

---

25.2 Capacity To Ship Packages Within D Days (LC 1011)

Đề bài

Cho weights[] (theo thứ tự), số ngày days. Tìm capacity nhỏ nhất của ship để chuyển hết hàng trong days ngày (mỗi ngày 1 chuyến, ship phải chở package liên tục theo thứ tự).

Ví dụ

Input:  weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

Ràng buộc

• 1 <= len(weights) <= 5·10^4
• 1 <= weights[i] <= 500
• 1 <= days <= len(weights)

Clarifying questions

• Một item nặng > capacity? → Bound lo = max(weights) đảm bảo không xảy ra.

Hướng tiếp cận

Đáp án cap ∈ [max(weights), sum(weights)]. (cap < max → không chở được package lớn nhất; cap = sum → 1 ngày xong.)

Predicate: “với cap này, chuyển hết trong ≤ days ngày?” → greedy đếm ngày.

Code Python 3

from typing import List

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:
        def can_ship(cap: int) -> bool:
            d = 1
            cur = 0
            for w in weights:
                if cur + w > cap:
                    d += 1
                    cur = 0
                cur += w
            return d <= days

        lo, hi = max(weights), sum(weights)
        while lo < hi:
            mid = (lo + hi) // 2
            if can_ship(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

Phân tích độ phức tạp

• Thời gian: O(n log(sum_weights)). Bộ nhớ: O(1).

Bình luận

• Bound chuẩn: lo = max(weights) (không bỏ qua được), hi = sum(weights).

Bài tự luyện liên quan

• LC 410 - Split Array Largest Sum (bài 25.3, cùng pattern).

---

25.3 Split Array Largest Sum (LC 410)

Đề bài

Cho nums (non-negative), số k. Chia mảng thành k subarray liên tục không rỗng. Tìm cách chia sao cho max sum subarray là nhỏ nhất.

Ví dụ

Input:  nums = [7,2,5,10,8], k = 2
Output: 18    (chia [7,2,5] và [10,8])

Ràng buộc

• 1 <= len(nums) <= 1000
• 0 <= nums[i] <= 10^6
• 1 <= k <= len(nums)

Clarifying questions

• k > len(nums)? → Theo đề: 1 ≤ k ≤ len.

Hướng tiếp cận

Y hệt 25.2! Đáp án = max sum. check(cap) = “chia được thành ≤ k subarray với mỗi subarray sum ≤ cap?”.

Code Python 3

from typing import List

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def can_split(cap: int) -> bool:
            groups = 1
            cur = 0
            for x in nums:
                if cur + x > cap:
                    groups += 1
                    cur = 0
                cur += x
            return groups <= k

        lo, hi = max(nums), sum(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if can_split(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

Phân tích độ phức tạp

• Thời gian: O(n · log(sum)).
• Bộ nhớ: O(1).

Bình luận

• Cùng pattern với 25.2 - chứng tỏ “search on answer” là ngôn ngữ, không phải trick riêng.
• Alternative - DP O(n² · k): chậm hơn nhiều cho LC 410.

Bài tự luyện liên quan

• LC 1011 - Capacity To Ship Packages.
• LC 1231 - Divide Chocolate.

---

25.4 Find K-th Smallest Pair Distance (LC 719)

Đề bài

Cho nums. Tính tất cả khoảng cách |nums[i] - nums[j]| với i < j. Trả về khoảng cách nhỏ thứ k.

Ví dụ

Input:  nums=[1,3,1], k=1
Output: 0

Ràng buộc

• n == len(nums)
• 2 <= n <= 10^4
• 0 <= nums[i] <= 10^6
• 1 <= k <= n·(n-1)/2

Clarifying questions

• nums có duplicate? → Có; sliding window vẫn đúng.

Hướng tiếp cận

Brute force: tạo tất cả C(n, 2) khoảng cách, sort, lấy thứ k. O(n² log n²). TLE với n = 10^4.

Search on answer + Sliding window đếm: - Sort nums. Đáp án ∈ [0, max - min]. - check(d) = “có ≥ k cặp có khoảng cách ≤ d?” - Đếm cặp bằng sliding window: với mỗi right, mở rộng left đến khi nums[right] - nums[left] <= d. Số cặp tạo thành = right - left.

Code Python 3

from typing import List

class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()

        def count_le(d: int) -> int:
            cnt = 0
            left = 0
            for right in range(len(nums)):
                while nums[right] - nums[left] > d:
                    left += 1
                cnt += right - left
            return cnt

        lo, hi = 0, nums[-1] - nums[0]
        while lo < hi:
            mid = (lo + hi) // 2
            if count_le(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

Phân tích độ phức tạp

• Thời gian: O(n log n + log(max_d) · n).
• Bộ nhớ: O(1).

Bình luận

• Sliding window đếm cặp là kỹ thuật phụ trợ rất hay đi cùng search on answer.

Bài tự luyện liên quan

• LC 668 - Kth Smallest in Multiplication Table.
• LC 2616 - Minimize Maximum Difference of Pairs.

---

25.5 Median of Two Sorted Arrays (LC 4)

Đề bài

Cho 2 mảng sort nums1, nums2. Tìm median của 2 mảng gộp lại. O(log(m+n)).

Ví dụ

Input:  nums1=[1,3], nums2=[2]
Output: 2.0
Giải thích: Median của [1,2,3] = 2

Ràng buộc

• nums1.length == m
• nums2.length == n
• 0 <= m, n <= 1000

Clarifying questions

• nums1, nums2 rỗng? → Theo đề: ít nhất 1 không rỗng.

Hướng tiếp cận

Binary search trên partition. Tìm i (chia nums1 ở vị trí i) và j = (m + n + 1) // 2 - i (chia nums2) sao cho:

• nums1[i-1] <= nums2[j] và nums2[j-1] <= nums1[i].

Khi tìm được, median = max(left) (nếu tổng lẻ) hoặc (max(left) + min(right)) / 2 (chẵn).

Đảm bảo binary search trên mảng ngắn hơn để O(log min(m, n)).

Code Python 3

from typing import List

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # Đảm bảo nums1 ngắn hơn.
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        half = (m + n + 1) // 2
        INF = float('inf')

        lo, hi = 0, m
        while lo <= hi:
            i = (lo + hi) // 2
            j = half - i
            left1 = nums1[i - 1] if i > 0 else -INF
            right1 = nums1[i] if i < m else INF
            left2 = nums2[j - 1] if j > 0 else -INF
            right2 = nums2[j] if j < n else INF
            if left1 <= right2 and left2 <= right1:
                if (m + n) % 2:
                    return max(left1, left2)
                return (max(left1, left2) + min(right1, right2)) / 2
            elif left1 > right2:
                hi = i - 1
            else:
                lo = i + 1
        return 0.0

Phân tích độ phức tạp

• Thời gian: O(log min(m, n)). Bộ nhớ: O(1).

Bình luận

• Bài Hard kinh điển - chìa khoá là nhận ra đây là binary partition (chia 2 mảng đã sort thành nửa nhỏ + nửa lớn), không phải search-on-answer.
• Bẫy: sentinel ±INF để xử lý boundary i = 0 hoặc i = m.

Bài tự luyện liên quan

• LC 1064 - Fixed Point.

---

25.6 Aggressive Cows (bài kinh điển)

Đề bài

Cho n chuồng tại vị trí pos[i] (đã sort) và c con bò. Đặt mỗi con vào 1 chuồng sao cho khoảng cách nhỏ nhất giữa 2 con là lớn nhất. Trả về khoảng cách đó.

Ví dụ

Input:  pos = [1, 2, 4, 8, 9], c = 3
Output: 3
Giải thích: đặt 1, 4, 8 → min distance = 3.

Ràng buộc

• 2 <= n <= 10^5
• 2 <= c <= n
• 0 <= pos[i] <= 10^9

Clarifying questions

• c > n? → Không xảy ra (đặt ≤ n con).

Hướng tiếp cận

Đáp án d ∈ [0, max - min]. Predicate: “đặt được c con với khoảng cách ≥ d?” → greedy: đặt con đầu ở pos đầu tiên, kế tiếp ở pos ≥ pos_trước + d.

Code Python 3

from typing import List

class Solution:
    def aggressiveCows(self, pos: List[int], c: int) -> int:
        pos.sort()

        def can_place(d: int) -> bool:
            placed = 1
            last = pos[0]
            for p in pos[1:]:
                if p - last >= d:
                    placed += 1
                    last = p
                    if placed >= c:
                        return True
            return False

        lo, hi = 0, pos[-1] - pos[0]
        while lo < hi:
            mid = (lo + hi + 1) // 2     # search "last True" → ceil mid
            if can_place(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

Phân tích độ phức tạp

• Thời gian: O(n log n + n log(max_d)).
• Bộ nhớ: O(1).

Bình luận

• “last True” pattern: mid = (lo + hi + 1) // 2 (ceil), lo = mid khi thoả. Khác với “first True” thông thường.
• Bài đại biểu cho phong cách search on answer.

Bài tự luyện liên quan

• LC 2517 - Maximum Tastiness of Candy Basket.

Tóm tắt chương & Quyết định

Search on Answer - universal table

Bài	Đáp số tìm	lo, hi	Predicate can(x)	Mục tiêu
Koko (LC 875)	tốc độ k	1, max(piles)	tổng giờ ≤ H	min x sao cho can(x)
Ship (LC 1011)	capacity	max(w), sum(w)	giao trong ≤ D ngày	min
Split Array (LC 410)	largest subarray sum	max(arr), sum(arr)	chia được ≤ m phần	min
Aggressive Cows	khoảng cách d	1, max - min	đặt được ≥ C bò	max x sao cho can(x)
Magnetic Force (LC 1552)	force	1, max - min	đặt được ≥ m	max

Khung chung (first-true / last-true):

# first-true monotonic: F F F T T T → trả T đầu tiên
while lo < hi:
    mid = (lo + hi) // 2
    if can(mid): hi = mid
    else: lo = mid + 1
return lo

Predicate monotonic - chứng minh

Phải kiểm chứng can(x) đơn điệu theo x: - Koko: k lớn → ăn nhanh hơn → tổng giờ giảm ⇒ can đơn điệu tăng. - Aggressive Cows: d lớn → khó đặt hơn → số bò đặt được giảm ⇒ can đơn điệu giảm.

Median of Two Sorted Arrays - KHÔNG phải search on answer

Đây là binary partition: tìm i, j sao cho A[..i] ∪ B[..j] là nửa nhỏ. Pattern khác hẳn, đừng ép vào template chung.

Aggressive Cows - feasibility

positions sorted: [1, 2, 4, 8, 9]    cows c = 3, d = ?
d = 3 ⇒ pick 1, 4, 8 ✅ (3 con)
d = 4 ⇒ pick 1, 8     (chỉ 2 con) ❌
⇒ max d sao cho ≥ 3 con = 3

---