Binary search — Invariant, lower/upper bound và search-on-answer

TL;DR: Binary search tìm điểm chuyển tiếp (transition point) trên không gian monotonic — không nhất thiết là sorted array mà là bất kỳ không gian nào có predicate dạng [F F F T T T]. Convention half-open [lo, hi) với mid = lo + (hi-lo)/2 tránh ba lỗi kinh điển: overflow, off-by-one, và infinite loop. Lower bound (predicate >=) trả về vị trí đầu tiên của target; upper bound (predicate >) trả về một vị trí sau target cuối cùng — chỉ khác một ký tự so sánh. Search-on-answer áp dụng binary search lên không gian câu trả lời số học: O(N log(hi-lo)) thay vì brute force O(N * hi).

Tutorial binary search dạy xong trong 5 phút — nhưng khảo sát nhanh code review thực tế cho thấy 90% implementation đầu tay bị reject vì ít nhất 1 trong 5 lỗi: (1) mid = (lo+hi)/2 gây overflow, (2) off-by-one trong loop condition, (3) infinite loop khi lo == hi - 1, (4) nhầm lower bound với upper bound, (5) không xử lý đúng khi có duplicate. Joshua Bloch — tác giả Effective Java — từng chỉ ra lỗi overflow tồn tại trong JDK Arrays.binarySearch suốt 9 năm (1998–2006) trước khi được fix.

Bài này dạy binary search bằng invariant — biết invariant đúng thì mọi variant (lower bound, upper bound, search-on-answer) viết được trong 1 phút mà không bug.

1. Analogy — Tra từ điển giấy

Bạn mở từ điển giấy tìm từ "serendipity". Thay vì lật từng trang từ đầu, bạn mở ra tầm giữa — thấy trang chữ "M". Biết "S" đứng sau "M" nên lật tiếp về phía sau. Lần tiếp theo mở ra chữ "R" — tiếp tục lật sau. Rồi "T" — lật trước. Mỗi lần loại bỏ một nửa số trang còn lại, và sau khoảng 20 bước bạn tìm thấy "serendipity" trong 500 nghìn từ.

Cơ chế này hoạt động được vì từ điển đã được sắp xếp theo alphabet. Đây chính là điều kiện tiên quyết của binary search: dữ liệu phải monotonic — có một ngưỡng tách phần "không thoả mãn" và phần "thoả mãn".

2. Prerequisite — Monotonic predicate

Binary search không yêu cầu sorted array. Yêu cầu thật sự là monotonic predicate: tồn tại một điểm split sao cho tất cả phần tử bên trái trả về false, tất cả phần tử bên phải (kể cả điểm split) trả về true. Không có phần tử true nào xuất hiện trước phần tử false nào.

Không gian predicate: [F F F F F T T T T T]
                                 ^
                             điểm chuyển tiếp -- đây là thứ binary search tìm

Ba ví dụ minh họa:

Ví dụ 1 — Sorted array tìm target: Array [2, 5, 8, 12, 16, 23, 38], tìm 12. Predicate P(i) = arr[i] >= 12.

Giá trị predicate: [F F F T T T T]
                          ^
                     index 3 = first T = vị trí của 12

Ví dụ 2 — Tìm phần tử đầu tiên bằng 1 trong mảng nhị phân: Array [0, 0, 0, 1, 1, 1, 1]. Predicate P(i) = arr[i] = 1.

Giá trị predicate: [F F F T T T T]
                          ^
                     index 3 = lần xuất hiện đầu tiên của 1

Ví dụ 3 — Search-on-answer (không phải sorted array): "Capacity tối thiểu để ship hết hàng trong D ngày." Predicate P(c) = canShip(capacity=c, days=D). Monotonic: capacity lớn hơn → số ngày cần ít hơn → dễ thoả hơn.

Predicate trên không gian capacity: [F F F F T T T T]
                                              ^
                                      capacity tối thiểu hợp lệ

Điểm mấu chốt: binary search tìm điểm chuyển tiếp — chỗ predicate đổi từ false sang true. Sorted array chỉ là trường hợp đặc biệt khi predicate là arr[i] >= target.

3. Implementation chuẩn — Invariant-driven

Invariant được chọn: "câu trả lời luôn nằm trong [lo, hi)" — lo inclusive, hi exclusive.

Tại sao half-open [lo, hi) tốt hơn [lo, hi]?

• Khởi tạo tự nhiên: lo = 0; hi = n — cả array.
• Loop condition while lo < hi dừng khi lo == hi — một điểm duy nhất, không cần check thêm.
• Không có infinite loop khi lo == hi - 1 (vấn đề của [lo, hi] nếu viết lo = mid).

-- Tìm chỉ số đầu tiên i mà predicate(i) là true.
-- Tiền đề: predicate là monotonic -- toàn false rồi toàn true.
-- Hậu đề: trả về lo == hi == chỉ số true đầu tiên.
--          Trả về n nếu không có phần tử nào thoả predicate.
lowerBound(A, target):
    lo <- 0
    hi <- A.length        -- half-open: [lo, hi)

    while lo < hi:
        mid <- lo + (hi - lo) / 2    -- tránh overflow (lo+hi) / 2

        if A[mid] >= target:
            hi <- mid                -- mid có thể là đáp án, giữ lại trong khoảng
        else:
            lo <- mid + 1            -- mid chắc chắn không phải đáp án

    return lo    -- lo == hi == điểm chuyển tiếp

Time: O(log n) Space: O(1)

graph TD
    INIT["lo=0, hi=n"]
    CHECK{"lo < hi?"}
    MID["mid = lo + (hi-lo)/2"]
    PRED{"A[mid] >= target?"}
    HI["hi = mid"]
    LO["lo = mid + 1"]
    DONE["Trả về lo (điểm chuyển tiếp)"]

    INIT --> CHECK
    CHECK -- "có" --> MID
    CHECK -- "không" --> DONE
    MID --> PRED
    PRED -- "đúng" --> HI
    PRED -- "sai" --> LO
    HI --> CHECK
    LO --> CHECK

Trace qua ví dụ: A = [2, 5, 8, 12, 16, 23, 38], target = 12.

lo=0, hi=7:  mid=3, A[3]=12 >= 12  -> hi=3
lo=0, hi=3:  mid=1, A[1]=5  < 12   -> lo=2
lo=2, hi=3:  mid=2, A[2]=8  < 12   -> lo=3
lo=3, hi=3:  vòng lặp kết thúc (lo == hi)
return 3   -- A[3] = 12, đúng

Tại sao invariant đảm bảo correctness? Mỗi bước giảm hi - lo ít nhất 1:

• Nếu predicate true tại mid: hi = mid. Vì mid < hi, nên hi giảm → range thu hẹp.
• Nếu predicate false tại mid: lo = mid + 1. Vì mid >= lo, nên lo tăng → range thu hẹp.

Khi lo == hi, loop dừng. lo là transition point — mọi index trước lo là false, mọi index từ lo trở đi là true.

4. 5 lỗi kinh điển và cách phòng

4.1 Overflow trong (lo + hi) / 2

Với lo = 1_000_000_000 và hi = 2_000_000_000, phép lo + hi = 3_000_000_000 vượt giới hạn số nguyên 32-bit (MAX = 2_147_483_647) → kết quả âm → index sai.

-- WRONG: overflow khi lo + hi > giới hạn int 32-bit
mid <- (lo + hi) / 2

-- CORRECT: không bao giờ overflow
mid <- lo + (hi - lo) / 2
-- Vì hi >= lo, (hi - lo) không âm và tối đa là MAX_INT

Lỗi này tồn tại trong JDK Arrays.binarySearch từ 1998 đến 2006 (Joshua Bloch phát hiện và report, fix trong Java 6).

4.2 Off-by-one trong loop condition

Convention [lo, hi) (half-open) và [lo, hi] (closed) yêu cầu loop condition khác nhau:

-- Convention [lo, hi) -- half-open, KHUYẾN NGHỊ
while lo < hi: ...
-- Vòng lặp kết thúc khi lo == hi -- đúng một ứng viên

-- Convention [lo, hi] -- closed
while lo <= hi: ...
-- Vòng lặp kết thúc khi lo > hi -- khoảng rỗng

Trộn lẫn hai convention trong cùng một hàm là nguồn gốc của off-by-one. Chọn một convention và dùng nhất quán cho mọi binary search.

4.3 Infinite loop khi lo == hi - 1

Lỗi này chỉ xuất hiện với convention [lo, hi] khi viết lo = mid thay vì lo = mid + 1:

-- BUG: infinite loop với closed interval [lo, hi]
while lo <= hi:
    mid <- lo + (hi - lo) / 2
    if predicate(mid):
        hi <- mid - 1
    else:
        lo <- mid    -- BUG: khi lo == hi - 1, mid == lo, lo không tăng
-- Khi lo=5, hi=6: mid=5, nếu predicate false -> lo=5 lại -> vòng lặp vô hạn

Với convention [lo, hi) và lo = mid + 1, điều này không xảy ra vì mid luôn nhỏ hơn hi, và mid + 1 luôn lớn hơn mid.

4.4 Lower bound vs upper bound

Sự khác biệt chỉ nằm ở một ký tự so sánh:

-- Lower bound: chỉ số đầu tiên i mà A[i] >= target
-- = lần xuất hiện đầu tiên của target (hoặc insertion point nếu không có)
lowerBound(A, target):
    lo <- 0;  hi <- A.length
    while lo < hi:
        mid <- lo + (hi - lo) / 2
        if A[mid] >= target: hi <- mid     -- predicate: >=
        else: lo <- mid + 1
    return lo

-- Upper bound: chỉ số đầu tiên i mà A[i] > target
-- = một vị trí sau lần xuất hiện cuối cùng của target
upperBound(A, target):
    lo <- 0;  hi <- A.length
    while lo < hi:
        mid <- lo + (hi - lo) / 2
        if A[mid] > target: hi <- mid      -- predicate: > (chỉ khác đây!)
        else: lo <- mid + 1
    return lo

Time: O(log n) Space: O(1)

Với array [1, 2, 2, 2, 3] và target = 2:

• lowerBound trả về 1 (index đầu tiên có giá trị bằng 2).
• upperBound trả về 4 (index đầu tiên có giá trị lớn hơn 2).
• Số lần xuất hiện của 2: upperBound - lowerBound = 4 - 1 = 3.

4.5 Duplicate handling

Naive binary search trả về một index bất kỳ trong run của duplicates — không phải first, không phải last. Nếu cần xác định chính xác vị trí:

-- Tìm lần xuất hiện đầu tiên của target -- dùng lowerBound, sau đó verify
findFirst(A, target):
    pos <- lowerBound(A, target)
    if pos < A.length AND A[pos] = target: return pos
    return -1   -- không tìm thấy

-- Tìm lần xuất hiện cuối cùng của target -- dùng upperBound - 1, sau đó verify
findLast(A, target):
    pos <- upperBound(A, target) - 1
    if pos >= 0 AND A[pos] = target: return pos
    return -1   -- không tìm thấy

Time: O(log n) Space: O(1)

5. Search-on-answer pattern

5.1 Ý tưởng

Thay vì binary search trên array có sẵn, binary search trên không gian câu trả lời. Áp dụng khi:

1. Câu trả lời là một giá trị số trong khoảng [lo, hi] xác định được.
2. Tồn tại hàm predicate(x) kiểm tra "x có phải câu trả lời hợp lệ không?"
3. Predicate là monotonic: nếu x hợp lệ thì mọi y > x cũng hợp lệ (hoặc ngược lại).

5.2 Bài kinh điển — Capacity tối thiểu để ship hàng trong D ngày

Đề bài: Cho mảng weights gồm n gói hàng và số ngày days. Mỗi ngày ship theo đúng thứ tự trong mảng. Tìm capacity tối thiểu của tàu để ship hết trong days ngày.

Monotonic property: capacity càng lớn → số ngày cần càng ít → nếu capacity c đủ, thì c+1 cũng đủ. Predicate P(c) = canShip(c, days) là monotonic.

-- Kiểm tra nếu capacity cho phép ship hết trong days ngày.
canShip(weights, capacity, days):
    daysNeeded  <- 1
    currentLoad <- 0

    for each weight trong weights:
        if currentLoad + weight > capacity:
            daysNeeded  <- daysNeeded + 1    -- bắt đầu ngày mới
            currentLoad <- 0
        currentLoad <- currentLoad + weight

    return daysNeeded <= days

-- Time: O(n) -- một lượt qua mảng

-- Tìm capacity tối thiểu để ship hết hàng trong days ngày.
shipWithinDays(weights, days):
    lo <- max(weights)       -- capacity ít nhất bằng gói nặng nhất
    hi <- sum(weights)       -- tối đa ship hết trong một ngày

    -- Binary search: tìm capacity nhỏ nhất mà canShip trả về true
    while lo < hi:
        mid <- lo + (hi - lo) / 2
        if canShip(weights, mid, days):
            hi <- mid              -- mid đủ, thử nhỏ hơn
        else:
            lo <- mid + 1          -- mid quá nhỏ, cần lớn hơn

    return lo    -- capacity tối thiểu hợp lệ

-- Time: O(n * log(sum - max))  Space: O(1)

Ví dụ: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5 → kết quả 15.

Complexity: canShip là O(n). Binary search chạy O(log(sum - max)) lần. Tổng: O(n * log(sum)). Với n = 500, sum cỡ 50000 → khoảng 500 * 17 = 8500 operations — cực nhanh so với brute force O(n * sum) = 25_000_000.

Các bài cùng pattern:

• Koko Eating Bananas — minimum eating speed.
• Split Array Largest Sum — minimum largest sum.
• Minimize Max Distance to Gas Station.

6. Pitfall bổ sung

Pitfall 1 — Float binary search và convergence

Với binary search trên số thực, loop while lo < hi không dừng được vì float precision:

-- WRONG: có thể không dừng do float precision
lo <- 0.0;  hi <- 1e9
while lo < hi:          -- lo và hi có thể không bằng nhau chính xác
    mid <- (lo + hi) / 2.0
    ...

-- BETTER: số lần lặp cố định
-- Sau 100 lần lặp, khoảng thu hẹp hệ số 2^100 -- đủ chính xác
lo <- 0.0;  hi <- 1e9
for iter <- 0 đến 99:
    mid <- (lo + hi) / 2.0
    if predicate(mid): hi <- mid
    else: lo <- mid
-- lo ≈ hi ≈ đáp án với độ chính xác ~ 1e9 / 2^100 ≈ 8e-22

-- ALTERNATIVE: dừng khi khoảng đủ nhỏ (chọn epsilon cẩn thận)
while hi - lo > 1e-9:
    mid <- (lo + hi) / 2.0
    if predicate(mid): hi <- mid
    else: lo <- mid

Số lần lặp cố định (100) an toàn hơn epsilon check: không cần biết trước epsilon phù hợp, không có rủi ro loop không dừng khi epsilon quá nhỏ so với giá trị tuyệt đối của lo/hi.

Pitfall 2 — Sorted descending array

Binary search trên array giảm dần yêu cầu flip predicate:

-- Array giảm dần: A[mid] <= target (không phải >=)
lowerBoundDesc(A, target):
    lo <- 0;  hi <- A.length
    while lo < hi:
        mid <- lo + (hi - lo) / 2
        if A[mid] <= target: hi <- mid     -- flipped: <= thay vì >=
        else: lo <- mid + 1
    return lo

Dễ quên khi viết vội — luôn kiểm tra xem array đang ascending hay descending trước khi chọn predicate.

Pitfall 3 — Predicate có side effect hoặc chậm

Binary search gọi predicate O(log n) lần. Nếu predicate có side effect (write DB, update state) hoặc tốn kém (network call, full scan):

-- PROBLEMATIC: predicate tốn kém được gọi O(log n) lần
while lo < hi:
    mid <- lo + (hi - lo) / 2
    if expensiveNetworkCheck(mid): hi <- mid   -- gọi ~30 lần cho n=10^9
    else: lo <- mid + 1

Trước khi áp dụng binary search, đảm bảo predicate là pure function (no side effect) và đủ nhanh để nhân O(log n) vẫn chấp nhận được.

7. Ứng dụng thực tế

Database B+tree index: mỗi node trong B+tree là một sorted array of keys. Tìm kiếm trong một node = binary search trên array nhỏ (thường 100–1000 keys). Bài 07 sẽ deep dive B+tree structure và tại sao database chọn B+tree thay vì hash index.

Git bisect: git bisect good/bad thực hiện binary search trên commit history để tìm commit gây regression. Predicate = "build/test pass tại commit này?" Với 1000 commit, chỉ cần khoảng 10 bước kiểm tra thay vì 1000. Đây là search-on-answer với không gian là tập commit đã sắp xếp theo thời gian.

Production capacity planning: "minimum số instance để giữ p99 latency dưới 200ms". Predicate P(n) = canHandle(n instances, current traffic, latency dưới 200ms) — monotonic: nhiều instance hơn → latency thấp hơn. Binary search trên [1, maxInstances] tìm minimum viable fleet size.

Math library — sqrt, log, exp: căn bậc hai có thể implement bằng binary search: tìm y trong [0, x] sao cho y*y >= x. Predicate y*y >= x là monotonic trên y. Thực tế nhiều runtime dùng Newton-Raphson (hội tụ nhanh hơn) nhưng binary search là cách dễ hiểu nhất để giải thích ý tưởng.

8. Deep Dive

9. Tóm tắt

• Binary search yêu cầu monotonic predicate — không nhất thiết sorted array. Predicate P(i) phải là [F F F ... T T T] không có T trước F.
• Invariant [lo, hi) half-open là convention an toàn nhất: khởi tạo lo=0, hi=n, loop while lo < hi, kết thúc lo == hi == transition point.
• Overflow trong (lo+hi)/2 là lỗi có tiền lệ trong JDK. Luôn dùng lo + (hi-lo)/2.
• Lower bound (predicate >=) trả về vị trí đầu tiên của target. Upper bound (predicate >) trả về một vị trí sau target cuối cùng. Chỉ khác nhau ở một ký tự so sánh.
• Search-on-answer áp dụng khi câu trả lời là số trong khoảng xác định và predicate monotonic — không cần array có sẵn. Complexity O(N log (hi-lo)).
• Float binary search dùng iteration count cố định (100 iterations) thay vì convergence test để tránh non-termination.

10. Tự kiểm tra

Bài tiếp theo: BST — insert/search/delete + balance