Binary search và các biến thể: lower bound, mảng xoay, tìm theo đáp án

1. Tổng quan

Binary search là thuật toán tìm kiếm trên dữ liệu đã sắp xếp với độ phức tạp O(log n). Ý tưởng rất đơn giản, nhưng cài đặt lại dễ sai: lặp vô hạn, lệch một đơn vị (off-by-one), tràn số khi tính mid.

Bài này đi từ phiên bản cơ bản tới các biến thể hay gặp: tìm vị trí đầu/cuối của phần tử trùng, đếm số lần xuất hiện, tìm trong mảng bị xoay, và binary search trên đáp án. Đọc xong, bạn sẽ có một bộ khung cài đặt ít lỗi, kèm test để kiểm chứng.

2. Binary search cơ bản

Giả sử bạn có mảng giá sản phẩm đã sắp xếp tăng dần và cần tìm vị trí của một mức giá:

public final class PriceSearch {

    public static int search(int[] prices, int target) {
        int lo = 0;
        int hi = prices.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (prices[mid] == target) {
                return mid;
            }
            if (prices[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] prices = {100, 150, 200, 350, 500};
        System.out.println(search(prices, 350));
        System.out.println(search(prices, 300));
    }
}

Giải thích:

• lo và hi tạo thành đoạn đóng [lo, hi]. Đây là vùng mà target có thể nằm trong đó.
• Điều kiện lo <= hi nghĩa là vòng lặp còn chạy khi đoạn còn ít nhất một phần tử.
• mid = lo + (hi - lo) / 2 tránh tràn số. Cách viết (lo + hi) / 2 sẽ tràn khi lo + hi vượt Integer.MAX_VALUE. Một cách tương đương là (lo + hi) >>> 1.
• Sau mỗi bước, ta loại mid khỏi đoạn (mid + 1 hoặc mid - 1), nên đoạn luôn thu hẹp và vòng lặp chắc chắn kết thúc.

Kết quả:

3
-1

Phiên bản này đủ dùng khi mảng không có phần tử trùng và bạn chỉ cần biết “có hay không”. Khi có phần tử trùng, nó trả về một vị trí bất kỳ trong nhóm trùng. Thường thì đó không phải điều bạn muốn.

3. Lower bound và upper bound

Hai biến thể quan trọng nhất là:

• lower bound: chỉ số đầu tiên có a[i] >= target.
• upper bound: chỉ số đầu tiên có a[i] > target.

Cả hai luôn trả về một chỉ số trong [0, n], kể cả khi target không có trong mảng. Chỉ số này chính là vị trí chèn để giữ mảng có thứ tự.

public final class Bounds {

    public static int lowerBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;              // đoạn nửa mở [lo, hi)
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    public static int upperBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

Khác biệt so với phiên bản cơ bản:

• Ta dùng đoạn nửa mở [lo, hi), nên hi khởi tạo bằng a.length và điều kiện lặp là lo < hi.
• Khi a[mid] thỏa điều kiện “đã đủ lớn”, ta gán hi = mid chứ không phải mid - 1, vì mid vẫn có thể là đáp án.
• Hai hàm chỉ khác nhau ở dấu < và <=.

Thử với mảng có phần tử trùng:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Bounds.lowerBound(prices, 200)); // 1
System.out.println(Bounds.upperBound(prices, 200)); // 4
System.out.println(Bounds.lowerBound(prices, 300)); // 4
System.out.println(Bounds.lowerBound(prices, 900)); // 6

1
4
4
6

Với 300, kết quả 4 cho biết nếu chèn 300 vào thì nó đứng trước 350. Với 900, kết quả bằng n nghĩa là mọi phần tử đều nhỏ hơn.

3.1. Vị trí đầu, vị trí cuối và số lần xuất hiện

Từ hai hàm trên, bạn suy ra ngay các bài toán quen thuộc:

public static int firstIndexOf(int[] a, int target) {
    int i = Bounds.lowerBound(a, target);
    return (i < a.length && a[i] == target) ? i : -1;
}

public static int lastIndexOf(int[] a, int target) {
    int i = Bounds.upperBound(a, target) - 1;
    return (i >= 0 && a[i] == target) ? i : -1;
}

public static int count(int[] a, int target) {
    return Bounds.upperBound(a, target) - Bounds.lowerBound(a, target);
}

Với prices ở trên và target = 200, ta được firstIndexOf = 1, lastIndexOf = 3, count = 3. Điểm cần nhớ: luôn kiểm tra biên i < a.length (hoặc i >= 0) trước khi đọc a[i].

3.2. Đếm phần tử trong một khoảng

Một ứng dụng thực tế là đếm số đơn hàng có giá trị trong [min, max]:

public static int countInRange(int[] sortedTotals, int min, int max) {
    return Bounds.upperBound(sortedTotals, max) - Bounds.lowerBound(sortedTotals, min);
}

Với {100, 200, 200, 200, 350, 500} và khoảng [150, 400], kết quả là 6 - ... ? Hãy tính: upperBound(400) = 5, lowerBound(150) = 1, nên kết quả là 4. Mỗi truy vấn chỉ tốn O(log n), không cần duyệt cả mảng.

4. Tìm kiếm trong mảng bị xoay

Mảng bị xoay là mảng đã sắp xếp rồi bị “cắt” ở một điểm và đổi chỗ hai nửa, ví dụ {40, 50, 60, 10, 20, 30}. Mảng này không còn tăng dần toàn bộ, nhưng ít nhất một nửa quanh mid vẫn có thứ tự. Ta dựa vào đó để quyết định đi về phía nào:

public static int searchRotated(int[] a, int target) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] == target) {
            return mid;
        }
        if (a[lo] <= a[mid]) {                 // nửa trái có thứ tự
            if (a[lo] <= target && target < a[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {                               // nửa phải có thứ tự
            if (a[mid] < target && target <= a[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

Giải thích:

• a[lo] <= a[mid] cho biết đoạn [lo, mid] tăng dần. Nếu target nằm trong khoảng giá trị của đoạn này, ta thu hẹp về bên trái. Ngược lại, ta sang phải.
• Trường hợp còn lại thì đoạn [mid, hi] tăng dần, và ta lập luận đối xứng.

System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 20));
System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 45));

4
-1

Lưu ý: Cài đặt này giả định mảng không có phần tử trùng. Với mảng như {2, 2, 2, 3, 2}, điều kiện a[lo] <= a[mid] không còn phân biệt được nửa nào có thứ tự. Khi đó bạn phải xử lý thêm trường hợp a[lo] == a[mid] bằng cách tăng lo lên một đơn vị, và độ phức tạp xấu nhất trở thành O(n).

5. Binary search trên đáp án

Đây là biến thể mạnh nhất. Nó không tìm trong mảng mà tìm giá trị nhỏ nhất thỏa một điều kiện. Điều kiện duy nhất để áp dụng là predicate phải đơn điệu: nếu x thỏa thì mọi giá trị lớn hơn x cũng thỏa. Nói cách khác, chuỗi kết quả có dạng false, false, ..., true, true.

Ta viết một hàm tổng quát:

import java.util.function.LongPredicate;

public final class AnswerSearch {

    /** Giá trị nhỏ nhất trong [lo, hi] làm ok trả về true. Giả định ok(hi) == true. */
    public static long firstTrue(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok.test(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

Hàm này có cùng cấu trúc với lowerBound. Thực ra lowerBound chỉ là trường hợp riêng với predicate a[i] >= target.

Áp dụng vào bài toán thực tế: kho có danh sách kiện hàng theo thứ tự cố định, cần giao hết trong maxDays ngày. Mỗi ngày xe chở các kiện liên tiếp, tổng khối lượng không vượt quá tải trọng xe. Hỏi tải trọng nhỏ nhất là bao nhiêu?

import java.util.Arrays;

public final class ShippingPlanner {

    public static long minCapacity(int[] weights, int maxDays) {
        long lo = Arrays.stream(weights).max().orElse(0);
        long hi = Arrays.stream(weights).asLongStream().sum();
        return AnswerSearch.firstTrue(lo, hi, cap -> canShip(weights, maxDays, cap));
    }

    static boolean canShip(int[] weights, int maxDays, long capacity) {
        int days = 1;
        long load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                days++;
                load = 0;
            }
            load += w;
        }
        return days <= maxDays;
    }

    public static void main(String[] args) {
        System.out.println(minCapacity(new int[]{3, 2, 2, 4, 1, 4}, 3));
    }
}

Giải thích:

• lo là kiện nặng nhất, vì xe phải chở được ít nhất một kiện bất kỳ. hi là tổng khối lượng, vì khi đó chỉ cần một ngày. Do vậy ok(hi) chắc chắn đúng.
• canShip mô phỏng tham lam: chất kiện lên xe cho tới khi quá tải thì sang ngày mới. Tải trọng càng lớn thì số ngày càng ít, nên predicate đơn điệu.
• Tổng chi phí là O(n · log(sum)), thay vì thử từng tải trọng.

6

Với tải trọng 6, lịch giao là [3, 2], [2, 4], [1, 4], đúng 3 ngày. Với tải trọng 5, ta cần 4 ngày, nên 5 không đạt.

Cùng khuôn này giải được nhiều bài khác: số thread tối thiểu để xử lý batch kịp hạn, giới hạn rate nhỏ nhất, căn bậc hai nguyên của một số.

6. Dùng thư viện chuẩn của Java

Java đã có sẵn Arrays.binarySearch và Collections.binarySearch. Bạn cần hiểu rõ giá trị trả về của chúng:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Arrays.binarySearch(prices, 350));
System.out.println(Arrays.binarySearch(prices, 300));

4
-5

• Khi tìm thấy, hàm trả về chỉ số của phần tử.
• Khi không thấy, hàm trả về -(insertionPoint) - 1. Ở đây vị trí chèn là 4, nên kết quả là -5. Để lấy lại vị trí chèn, bạn tính -(result) - 1.
• Khi có phần tử trùng, tài liệu không đảm bảo trả về vị trí nào trong nhóm trùng. Nếu cần vị trí đầu hoặc cuối, hãy dùng lowerBound/upperBound tự viết.

Với danh sách đối tượng, bạn truyền Comparator khớp với thứ tự đã sắp xếp:

record Order(String id, long total) {}

List<Order> orders = List.of(
        new Order("A1", 120), new Order("B7", 300), new Order("C3", 450));
int idx = Collections.binarySearch(
        orders, new Order("?", 300), Comparator.comparingLong(Order::total));
System.out.println(idx); // 1

Lưu ý: Collections.binarySearch trên LinkedList không đạt O(log n) vì truy cập theo chỉ số tốn O(n). Hãy dùng ArrayList hoặc mảng.

7. Kiểm thử

Thêm dependency JUnit 5 và AssertJ. Nếu dự án dùng spring-boot-starter-test thì cả hai đã có sẵn.

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.11.0</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.26.3</version>
    <scope>test</scope>
</dependency>

Viết test cho các trường hợp biên. Đây là nơi binary search hay hỏng nhất:

import org.junit.jupiter.api.Test;
import java.util.Random;
import java.util.stream.IntStream;
import static org.assertj.core.api.Assertions.assertThat;

class BoundsTest {

    private final int[] prices = {100, 200, 200, 200, 350, 500};

    @Test
    void lowerAndUpperBoundHandleDuplicates() {
        assertThat(Bounds.lowerBound(prices, 200)).isEqualTo(1);
        assertThat(Bounds.upperBound(prices, 200)).isEqualTo(4);
    }

    @Test
    void boundsReturnInsertionPointAtEdges() {
        assertThat(Bounds.lowerBound(prices, 50)).isZero();
        assertThat(Bounds.lowerBound(prices, 900)).isEqualTo(prices.length);
        assertThat(Bounds.lowerBound(new int[0], 1)).isZero();
    }

    @Test
    void lowerBoundMatchesLinearScan() {
        Random random = new Random(42);
        for (int round = 0; round < 1_000; round++) {
            int[] a = random.ints(random.nextInt(20), 0, 10).sorted().toArray();
            int target = random.nextInt(12) - 1;
            int expected = (int) IntStream.of(a).filter(x -> x < target).count();
            assertThat(Bounds.lowerBound(a, target)).isEqualTo(expected);
        }
    }

    @Test
    void minCapacityFindsSmallestFeasibleValue() {
        int[] weights = {3, 2, 2, 4, 1, 4};
        assertThat(ShippingPlanner.minCapacity(weights, 3)).isEqualTo(6);
        assertThat(ShippingPlanner.canShip(weights, 3, 5)).isFalse();
    }
}

Test lowerBoundMatchesLinearScan so sánh với cách đếm tuyến tính trên 1.000 mảng ngẫu nhiên, bao gồm cả mảng rỗng. Kiểu test đối chiếu này bắt lỗi off-by-one tốt hơn nhiều so với vài ví dụ viết tay.

8. Lỗi hay gặp và khi nào không nên dùng

Các lỗi phổ biến:

• Trộn hai quy ước đoạn. Bạn khởi tạo hi = n (nửa mở) nhưng lại lặp while (lo <= hi) và gán hi = mid - 1. Kết quả là đọc ra ngoài mảng. Hãy chọn một quy ước và giữ nhất quán.
• Lặp vô hạn. Nếu bạn viết lo = mid cùng với mid = (lo + hi) / 2, khi hi = lo + 1 thì mid == lo và đoạn không thu hẹp. Nếu thật sự cần lo = mid, hãy làm tròn lên: mid = lo + (hi - lo + 1) / 2.
• Tràn số khi tính mid hoặc khi tính tổng trong binary search trên đáp án. Dùng long cho các giá trị có thể lớn.
• Predicate không đơn điệu. Binary search vẫn trả về một con số, nhưng con số đó vô nghĩa. Hãy chứng minh tính đơn điệu trước khi áp dụng.

Khi nào không nên dùng binary search:

• Dữ liệu chưa sắp xếp và chỉ tìm một vài lần. Sắp xếp tốn O(n log n), còn tìm tuyến tính chỉ O(n).
• Bạn chỉ cần kiểm tra “có hay không” với nhiều lần tìm. Khi đó HashSet cho O(1) trung bình.
• Dữ liệu thay đổi liên tục, phải chèn và xóa nhiều. Giữ mảng có thứ tự sẽ tốn O(n) mỗi lần chèn. Hãy cân nhắc TreeMap/TreeSet, vốn có sẵn ceilingKey, floorKey, higherKey tương đương lower bound và upper bound.
• Mảng rất nhỏ, chỉ vài chục phần tử. Duyệt tuyến tính thường nhanh ngang hoặc hơn nhờ cache, và code đơn giản hơn.

9. Kết luận

Binary search không chỉ là “tìm phần tử trong mảng”. Khi nắm được lower bound và upper bound với đoạn nửa mở [lo, hi), bạn giải được các bài vị trí đầu/cuối, đếm phần tử và đếm theo khoảng chỉ bằng vài dòng. Mảng bị xoay cần thêm một bước xác định nửa có thứ tự. Binary search trên đáp án mở rộng kỹ thuật sang mọi bài toán có predicate đơn điệu.

Hãy giữ một quy ước đoạn duy nhất, dùng >>> hoặc lo + (hi - lo) / 2 để tránh tràn số, và luôn có test đối chiếu với cách tìm tuyến tính. Ba thói quen này loại bỏ gần hết lỗi mà binary search vẫn nổi tiếng là hay gây ra.