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

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.

Predicate space: [F F F F F T T T T T]
                              ^
                          transition point -- đâ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.

Predicate values: [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.

Predicate values: [F F F T T T T]
                         ^
                    index 3 = first occurrence of 1

Ví dụ 3 — Search-on-answer (không phải sorted array): "Minimum capacity to ship all packages within D days." 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. Không gian tìm kiếm là khoảng [max(weights), sum(weights)] — không phải array có sẵn.

Predicate over capacity space: [F F F F T T T T]
                                         ^
                                 minimum valid capacity

Điểm mấu chốt: binary search tìm điểm transition — 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).

// Find first index i where predicate(i) is true.
// Precondition: predicate is monotonic -- all false then all true.
// Postcondition: returns lo == hi == first true index.
//                Returns n if no element satisfies predicate.
public static int lowerBound(int[] arr, int target) {
    int lo = 0;
    int hi = arr.length;          // half-open: [lo, hi)

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;   // avoids (lo+hi) overflow

        if (arr[mid] >= target) {
            hi = mid;             // mid might be the answer, keep it in range
        } else {
            lo = mid + 1;         // mid is definitely not the answer
        }
    }

    return lo;   // lo == hi == transition point
}

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

lo=0, hi=7:  mid=3, arr[3]=12 >= 12  -> hi=3
lo=0, hi=3:  mid=1, arr[1]=5  < 12   -> lo=2
lo=2, hi=3:  mid=2, arr[2]=8  < 12   -> lo=3
lo=3, hi=3:  loop ends (lo == hi)
return 3   -- arr[3] == 12, correct

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 Integer.MAX_VALUE = 2_147_483_647 → kết quả âm → index sai → ArrayIndexOutOfBoundsException hoặc wrong result.

// WRONG: overflow when lo + hi > Integer.MAX_VALUE
int mid = (lo + hi) / 2;

// CORRECT: no overflow possible
int mid = lo + (hi - lo) / 2;
// Since hi >= lo, (hi - lo) is non-negative and at most Integer.MAX_VALUE

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). (hi - lo) / 2 equivalent với (lo + hi) / 2 về mặt toán học khi không overflow, nhưng an toàn hơn trong integer arithmetic.

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, RECOMMENDED
while (lo < hi) { ... }
// Loop ends when lo == hi -- exactly one candidate

// Convention [lo, hi] -- closed
while (lo <= hi) { ... }
// Loop ends when lo > hi -- empty range

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 with closed interval [lo, hi]
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (predicate(mid)) {
        hi = mid - 1;
    } else {
        lo = mid;    // BUG: when lo == hi - 1, mid == lo, lo stays unchanged
    }
}
// When lo=5, hi=6: mid=5, if predicate false -> lo=5 again -> infinite loop

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: first index i where arr[i] >= target
// = first occurrence of target (or insertion point if not present)
public static int lowerBound(int[] arr, int target) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] >= target) hi = mid;   // predicate: >=
        else lo = mid + 1;
    }
    return lo;
}

// Upper bound: first index i where arr[i] > target
// = one past last occurrence of target
public static int upperBound(int[] arr, int target) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] > target) hi = mid;    // predicate: > (only difference!)
        else lo = mid + 1;
    }
    return lo;
}

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í:

// Find first occurrence of target -- use lowerBound, then verify
public static int findFirst(int[] arr, int target) {
    int pos = lowerBound(arr, target);
    if (pos < arr.length && arr[pos] == target) return pos;
    return -1;  // not found
}

// Find last occurrence of target -- use upperBound - 1, then verify
public static int findLast(int[] arr, int target) {
    int pos = upperBound(arr, target) - 1;
    if (pos >= 0 && arr[pos] == target) return pos;
    return -1;  // not found
}

5. Java standard library

Arrays.binarySearch(int[], int) trong JDK:

// Simplified from OpenJDK Arrays.binarySearch -- the fix for overflow (2006):
private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
    int low  = fromIndex;
    int high = toIndex - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;   // unsigned right shift: avoids signed overflow
        int midVal = a[mid];
        if      (midVal < key) low  = mid + 1;
        else if (midVal > key) high = mid - 1;
        else                   return mid;  // found
    }
    return -(low + 1);  // not found: -(insertionPoint) - 1
}

Sau khi Bloch báo cáo overflow, OpenJDK fix bằng (low + high) >>> 1 — unsigned right shift thay vì signed division. Kết quả tương đương cho non-negative integers vì unsigned shift không propagate sign bit.

Return value khi không tìm thấy: -(insertionPoint) - 1. Encode âm để tránh ambiguity với index 0 (nếu trả về -insertionPoint, index 0 và "not found tại insertion point 0" đều trả về 0). Để recover insertion point: insertionPoint = -result - 1.

int[] arr = {1, 3, 5, 7, 9};
int result = Arrays.binarySearch(arr, 5);   // returns 2 (index of 5)
int result2 = Arrays.binarySearch(arr, 4);  // returns -3 -- insertionPoint = -(-3)-1 = 2
// arr[2] = 5 > 4, so 4 would be inserted at index 2 to maintain order

Các API khác trong JDK:

Collections.binarySearch trên LinkedList vẫn là O(n) vì get(i) là O(n) — dùng ArrayList hoặc mảng khi cần binary search thực sự O(log n).

6. Search-on-answer pattern

6.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).

6.2 Bài kinh điển — Capacity to Ship Packages Within D Days (LeetCode 1011)

Đề 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 (không được đảo thứ tự). Tìm capacity tối thiểu của tàu để ship hết trong days ngày.

Brute force: thử mọi capacity từ max(weights) đến sum(weights) — O(N * sum), quá chậm.

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

public class ShipPackages {

    // Check if given capacity allows shipping all packages within 'days' days.
    // Time: O(n) -- one pass through weights
    private static boolean canShip(int[] weights, int capacity, int days) {
        int daysNeeded = 1;
        int currentLoad = 0;

        for (int weight : weights) {
            if (currentLoad + weight > capacity) {
                daysNeeded++;         // start a new day
                currentLoad = 0;
            }
            currentLoad += weight;
        }

        return daysNeeded <= days;
    }

    // Find minimum capacity to ship all packages within 'days' days.
    // Time: O(N * log(sum - max)) -- binary search on answer space
    public static int shipWithinDays(int[] weights, int days) {
        int lo = 0;
        int hi = 0;

        for (int w : weights) {
            lo = Math.max(lo, w);     // capacity must be at least max single weight
            hi += w;                  // at most sum (ship everything in one day)
        }

        // Binary search: find first capacity where canShip is true
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, mid, days)) {
                hi = mid;             // mid works, try smaller
            } else {
                lo = mid + 1;         // mid too small, need bigger
            }
        }

        return lo;  // minimum valid capacity
    }

    public static void main(String[] args) {
        int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(shipWithinDays(weights, 5));  // 15
        System.out.println(shipWithinDays(weights, 1));  // 55 (ship all in one day)
    }
}

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 (LeetCode 875) — minimum eating speed.
• Split Array Largest Sum (LeetCode 410) — minimum largest sum.
• Minimize Max Distance to Gas Station (LeetCode 774).

7. Pitfall bổ sung

Pitfall 1 — Float binary search và convergence

Với binary search trên số thực (tìm căn bậc hai, nghiệm phương trình), lo < hi không dừng được vì float precision:

// WRONG: may never terminate due to float precision
double lo = 0.0, hi = 1e9;
while (lo < hi) {           // lo and hi may never be exactly equal
    double mid = (lo + hi) / 2.0;
    ...
}

// BETTER: fixed iteration count
// After 100 iterations, range shrinks by factor 2^100 -- more than enough precision
double lo = 0.0, hi = 1e9;
for (int iter = 0; iter < 100; iter++) {
    double mid = (lo + hi) / 2.0;
    if (predicate(mid)) hi = mid;
    else lo = mid;
}
// lo ~= hi ~= answer with precision ~1e9 / 2^100 ~= 8e-22

// ALTERNATIVE: epsilon-based stop (choose epsilon carefully)
while (hi - lo > 1e-9) {
    double mid = (lo + hi) / 2.0;
    if (predicate(mid)) hi = mid;
    else lo = mid;
}

Iteration count 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:

// Descending array: arr[i] <= target (not >=)
public static int lowerBoundDesc(int[] arr, int target) {
    int lo = 0, hi = arr.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= target) hi = mid;   // flipped: <= instead of >=
        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 to DB, update state) hoặc tốn kém (network call, full scan):

// PROBLEMATIC: predicate makes expensive call O(log n) times
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (expensiveNetworkCheck(mid)) hi = mid;   // called ~30 times for 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).
• O(1) hoặc đủ nhanh để nhân O(log n) vẫn chấp nhận được.

Nếu predicate là O(N) (như canShip), kết quả là O(N log N) — thường vẫn chấp nhận được, nhưng cần tính toán trước khi commit.

8. Ứ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). Vì node fit trong một disk page, toàn bộ binary search trong node chỉ cần một I/O. Module 3 bài 07 sẽ deep dive B+tree structure và tại sao MySQL 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 < 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: Math.sqrt(x) 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ế JVM dùng Newton-Raphson (hội tụ nhanh hơn) nhưng binary search là cách dễ hiểu nhất.

String matching — substring search: naive String.indexOf là O(n*m). KMP và Rabin-Karp giảm về O(n+m) bằng cách tránh recompute. Module 7 sẽ cover các thuật toán này — binary search không apply trực tiếp nhưng Rabin-Karp dùng hash function tương tự Module 3 bài 01.

9. Deep Dive

10. 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 hoặc (lo + hi) >>> 1.
• 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.
• Arrays.binarySearch trả về -(insertionPoint)-1 khi không tìm thấy — encoding âm tránh ambiguity với index 0.

11. Tự kiểm tra

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