BYNARY SEARCH

. Điều kiện áp dụng

Mảng đã sắp xếp

Hoặc bài toán có tính chất:

nếu x thỏa → mọi giá trị lớn hơn (hoặc nhỏ hơn) cũng thỏa

(→ monotonic)

Tìm vị trí x trong mảng tăng dần

int l = 0, r = n - 1;

while (l <= r) {

int m = (l + r) >> 1;

if (a[m] == x) return m;

if (a[m] < x) l = m + 1;

else r = m - 1;

}

return -1;

. Lowerbound / Upperbound

lower_bound: phần tử đầu tiên ≥ x

int l = 0, r = n;

while (l < r) {

int m = (l + r) >> 1;

if (a[m] < x) l = m + 1;

else r = m;

}

upper_bound: phần tử đầu tiên > x

int l = 0, r = n;

while (l < r) {

int m = (l + r) >> 1;

if (a[m] <= x) l = m + 1;

else r = m;

}

Đếm số phần tử = x:

upperbound - lowerbound

. Binary Search trên đáp án (quan trọng nhất)

Dạng:

Tìm giá trị nhỏ nhất/lớn nhất thỏa điều kiện

int l = L, r = R, ans = -1;

while (l <= r) {

int m = (l + r) >> 1;

if (check(m)) {

    ans = m;

    r = m - 1; // tìm min

} else {

    l = m + 1;

}

}

Nếu tìm max thì đổi: l = m + 1;

Ví dụ kinh điển

Chia gỗ / chia mảng / tối ưu

“Tìm max chiều dài”

“Tìm min thời gian”

“Tối ưu chi phí”

👉 Pattern:

đoán m

check xem có làm được không

. Binary Search số thực

double l = 0, r = 1e9;

for (int i = 0; i < 100; i++) {

double m = (l + r) / 2;

if (check(m)) r = m;

else l = m;

}