Binary Search — Tìm kiếm nhị phân

Binary Search cơ bản

Điều kiện: mảng đã sort.

public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // tránh overflow

        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1; // not found
}

Biến thể: Lower Bound

Tìm vị trí đầu tiên >= target:

public int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }

    return left;
}

Search on Answer

Binary search không chỉ dùng trên mảng — dùng trên không gian đáp án:

// Tìm số nguyên nhỏ nhất x sao cho f(x) = true
// f phải monotonic: false false false true true true
public int searchOnAnswer(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Key insight: Binary search áp dụng được khi có tính chất monotonic — một bên thỏa, một bên không. Không nhất thiết phải là mảng sorted.