Sắp xếp & Tìm kiếm nhị phân

Sắp xếp (sorting) đưa một dãy về thứ tự tăng/giảm; tìm kiếm nhị phân (binary search) tận dụng tính đã-sắp-xếp đó để định vị một phần tử hoặc một ngưỡng trong $O(\log N)$ thay vì quét tuyến tính $O(N)$. Kết hợp hai kỹ thuật này là nền tảng của vô số bài: từ "có tồn tại giá trị $x$ không?" đến "giá trị nhỏ nhất thoả mãn điều kiện là bao nhiêu?" (chặt nhị phân trên đáp án). Sắp xếp bằng std::sort mất $O(N\log N)$; sau đó mỗi truy vấn tìm kiếm chỉ $O(\log N)$.

Ý tưởng / Trực giác

Vì sao sắp xếp hữu ích?

Rất nhiều bài toán trở nên dễ khi dữ liệu có thứ tự: phần tử nhỏ nhất/lớn nhất nằm ở hai đầu, các giá trị bằng nhau nằm liền kề (dễ đếm/khử trùng lặp), và quan trọng nhất — ta có thể tìm kiếm nhị phân. std::sort dùng IntroSort (kết hợp QuickSort + HeapSort + InsertionSort) nên luôn đạt $O(N\log N)$ kể cả trường hợp xấu.

Vì sao tìm kiếm nhị phân đúng?

Tìm kiếm nhị phân dựa trên tính đơn điệu (monotonicity). Trong mảng tăng dần, nếu a[mid] < target thì mọi phần tử bên trái mid cũng < target, nên đáp án (nếu có) chỉ có thể nằm ở nửa phải. Mỗi bước loại bỏ được một nửa không gian tìm kiếm, nên sau ${\log }_{2}N$ bước khoảng tìm kiếm thu về một phần tử. Đây là lý do mảng bắt buộc phải đơn điệu — nếu không, việc "vứt bỏ một nửa" sẽ vứt nhầm cả đáp án.

Chặt nhị phân trên đáp án (binary search on the answer)

Đây là ứng dụng mạnh nhất. Nhiều bài hỏi "giá trị nhỏ nhất $x$ sao cho điều kiện $P(x)$ đúng". Nếu $P$ có dạng đơn điệu — tức $P$ sai với mọi $x$ nhỏ, rồi đúng với mọi $x$ đủ lớn:

x:     0  1  2  3  4  5  6  7  8
P(x):  F  F  F  F  F  T  T  T  T
                     ^
                     đáp án = ranh giới F→T

thì ta không cần thử từng giá trị; chỉ cần nhị phân để tìm ranh giới giữa vùng F và vùng T. Bí quyết: thay vì so sánh phần tử, ta gọi một hàm check(x) mô phỏng/kiểm tra tính khả thi. Miễn là check đơn điệu, thuật toán đúng.

Ví dụ chạy tay

Tìm kiếm nhị phân thường

Tìm target = 7 trong mảng đã sắp xếp. Ký hiệu l, r là biên, m là điểm giữa, vùng [...] là khoảng còn đang xét.

chỉ số:  0   1   2   3   4   5   6
giá trị: 1   3   5   7   9  11  13

Bước 1: l=0, r=6, m=3 → a[3]=7 == target  → tìm thấy tại chỉ số 3

Một ví dụ phải đi nhiều bước hơn, tìm target = 11:

giá trị: 1   3   5   7   9  11  13
         l               m       r        m=3, a[3]=7 < 11 → bỏ nửa trái, l=4
                             l   m   r     m=5, a[5]=11 == 11 → thấy tại chỉ số 5

Chặt nhị phân trên đáp án (bài "Bò nổi giận")

$N=7$ kiện cỏ ở vị trí (sau khi sắp) 1 3 8 10 18 20 25, có $K=2$ con bò, mỗi con bắn bán kính $R$ phủ đoạn dài $2R+1$. Tìm $R$ nhỏ nhất phủ hết. Hàm check(R) = "có thể phủ hết bằng $\le K$ con bò không?" được tính tham lam: luôn đặt con bò sao cho biên trái của đoạn trùng kiện cỏ nhỏ nhất chưa phủ.

R = 4 → mỗi con phủ đoạn dài 2*4+1 = 9
  vị trí:  1  3  8 10 18 20 25
  con 1 phủ [1..10]:   1 3 8 10  ✓ (4 kiện)
  con 2 phủ [18..27]:  18 20 25  ✓
  → dùng 2 con = K  → check(4) = TRUE

R = 3 → mỗi con phủ đoạn dài 7
  con 1 phủ [1..8]:    1 3 8       (kiện 10 chưa phủ)
  con 2 phủ [10..17]:  10
  con 3 phủ [18..25]:  18 20 25
  → cần 3 con > K=2  → check(3) = FALSE

Bảng check đơn điệu F F F F T T ... theo $R$, nên nhị phân trên $R$:

Đáp án là ranh giới F→T, tức $R=4$.

Cài đặt

Sắp xếp với std::sort

#include <bits/stdc++.h>
using namespace std;

vector<int> a = {5, 2, 8, 1, 9};
sort(a.begin(), a.end());                    // tăng dần: 1 2 5 8 9
sort(a.begin(), a.end(), greater<int>());    // giảm dần: 9 8 5 2 1

// Sắp xếp theo nhiều khoá: tăng theo first, nếu bằng thì giảm theo second
vector<pair<int,int>> v;
sort(v.begin(), v.end(), [](const auto& x, const auto& y) {
    if (x.first != y.first) return x.first < y.first;
    return x.second > y.second;              // hàm so sánh phải "đúng thứ tự yếu chặt"
});

Tìm kiếm nhị phân thủ công và bằng STL

// Tìm chỉ số của target trong mảng đã sắp tăng; trả -1 nếu không có
int binarySearch(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;        // tránh tràn so với (lo+hi)/2
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;   // đáp án ở nửa phải
        else                  hi = mid - 1;  // đáp án ở nửa trái
    }
    return -1;
}

// STL: lower_bound = vị trí đầu tiên >= target; upper_bound = đầu tiên > target
auto it = lower_bound(a.begin(), a.end(), target);
int idx = it - a.begin();                    // chỉ số; = a.size() nếu không có phần tử >= target
bool exists = (it != a.end() && *it == target);

Chặt nhị phân trên đáp án (tìm giá trị nhỏ nhất thoả mãn)

// check(x) phải đơn điệu: false...false, true...true theo x tăng dần
bool check(long long x) {
    // ... mô phỏng/kiểm tra x có khả thi không ...
    return true;
}

long long lo = 0, hi = 1e18;                 // hi đủ lớn để chắc chắn check(hi)=true
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (check(mid)) hi = mid;                // mid khả thi → thử nhỏ hơn nữa
    else            lo = mid + 1;            // mid không khả thi → phải lớn hơn
}
// lo == hi == đáp án nhỏ nhất thoả mãn check

Python

import bisect
a.sort()                          # tăng dần, in-place
b = sorted(a, reverse=True)       # bản sao giảm dần
a.sort(key=lambda x: (x[0], -x[1]))

i = bisect.bisect_left(a, x)      # vị trí đầu tiên >= x  (~ lower_bound)
j = bisect.bisect_right(a, x)     # vị trí đầu tiên > x   (~ upper_bound)
found = i < len(a) and a[i] == x

Độ phức tạp

Lưu ý: chặt nhị phân trên đáp án không giảm tổng độ phức tạp xuống $O(\log V)$ — chi phí thật là $\log V$ nhân chi phí một lần check. Nếu check là $O(N)$ thì tổng là $O(N\log V)$.

⚠️ Lỗi thường gặp

• Tìm kiếm nhị phân trên mảng CHƯA sắp xếp. Đây là lỗi nghiêm trọng nhất: thuật toán "vứt một nửa" dựa hoàn toàn vào tính đơn điệu. Mảng không sắp xếp ⇒ kết quả sai một cách ngẫu nhiên (đôi khi vẫn đúng với vài test nhỏ, rất khó debug). Luôn sort trước.
• Tràn số khi tính mid. Viết mid = (lo + hi) / 2 với lo, hi cỡ ${10}^9$ kiểu int sẽ tràn (lo+hi > $2^{31}$). Luôn dùng mid = lo + (hi - lo) / 2. Với chặt nhị phân trên đáp án có khoảng lớn, dùng long long.
• Vòng lặp vô hạn do cập nhật sai biên. Với khuôn while (lo < hi): nhánh đúng phải là hi = mid còn nhánh sai là lo = mid + 1. Nếu lỡ viết hi = mid - 1 ở nhánh đúng có thể bỏ sót đáp án; nếu viết lo = mid ở nhánh sai thì khi hi = lo + 1, mid luôn bằng lo và vòng lặp không bao giờ kết thúc. Khi đặt hi = mid, nhánh kia bắt buộc lo = mid + 1.
• check KHÔNG đơn điệu. Chặt nhị phân trên đáp án chỉ đúng khi check có dạng F...F T...T (hoặc ngược lại). Nếu hàm điều kiện "bật tắt" lung tung theo $x$, nhị phân sẽ rơi vào một ranh giới ngẫu nhiên. Phải chứng minh tính đơn điệu trước khi áp dụng.
• Chọn hi ban đầu quá nhỏ. Trong chặt nhị phân trên đáp án, nếu đáp án thật lớn hơn hi khởi tạo thì không bao giờ tìm thấy. Đặt hi đủ lớn để chắc chắn check(hi) = true (ví dụ tổng toàn bộ mảng, hoặc ${10}^{18}$).
• lower_bound trả về end(). Khi không có phần tử nào >= target, lower_bound trả a.end(); truy cập *it lúc này là hành vi không xác định. Luôn kiểm tra it != a.end() trước khi dereference.
• Hàm so sánh không hợp lệ làm sort crash. Comparator cho std::sort phải là strict weak ordering: với hai phần tử bằng nhau phải trả false (dùng <, không dùng <=). Comparator sai (ví dụ trả true cho cả cmp(a,b) và cmp(b,a)) gây lỗi runtime hoặc undefined behavior.

Biến thể / Mở rộng

• Tìm kiếm tam phân (ternary search): khi hàm là lồi/lõm (unimodal) thay vì đơn điệu, dùng tam phân để tìm cực trị trong $O(\log N)$.
• Hai con trỏ (two pointers) & cửa sổ trượt: sau khi sắp xếp, nhiều bài "tìm cặp tổng bằng $S$" giải được trong $O(N)$ bằng hai con trỏ thay vì nhị phân — xem Hai con trỏ.
• Nén toạ độ (coordinate compression): dùng sort + unique + lower_bound để ánh xạ giá trị lớn về chỉ số $[0,K)$, thường làm bước tiền xử lý cho Fenwick/Segment Tree.

Bài tập luyện

• Số Phân Biệt (distnum) — (Nghiệp dư) Đếm số giá trị phân biệt: sắp xếp rồi đếm các đoạn bằng nhau liền kề — bài khởi động cho thói quen "sort trước".
• Tối Đa Năng Suất (maxprod) — (Học việc) Sắp xếp mảng thời gian rồi với mỗi truy vấn dùng upper_bound/chặt nhị phân để đếm số trang trại kịp tham.
• Vé Hòa Nhạc (concerttic) — (Nghiệp dư) Mỗi khách lấy vé đắt nhất không vượt ngân sách: kinh điển cho upper_bound trên multiset đã sắp.
• Bò nổi giận - Silver (angrycows) — (Trung cấp) Chặt nhị phân trên đáp án $R$, với check(R) tham lam đặt bò — ví dụ mẫu cho kỹ thuật binary search on the answer.
• Chia Mảng (arraydiv) — (Trung cấp) Chia mảng thành $k$ đoạn sao cho tổng lớn nhất nhỏ nhất: bài mẫu kinh điển nhị phân trên đáp án với check tham lam đếm số đoạn.