Bỏ qua
Tuần 12

Tìm kiếm nhị phân

Độ khó
★★★★☆ Khó
Thời lượng
Khoảng 120 phút
Học trước
Sort, pair và comparator
Chủ đề
nhị phântìm kiếm
Trạng thái

Kiến thức cơ bản

Vì sao cần tìm kiếm nhị phân

Khi cần biết "có số x trong dãy không?", cách quen thuộc là duyệt từ đầu đến cuối dãy. Đó gọi là tìm kiếm tuần tự, mất khoảng n phép so sánh cho mỗi câu hỏi. Với n = 105 số và q = 105 câu hỏi, ta mất khoảng 1010 phép tính, chậm hơn quy ước 108 khi lập trình thi đấu rất nhiều.

Hãy chơi thử một trò chơi. Gấu Po nghĩ ra một số từ 1 đến 100, Thỏ phải đoán. Sau mỗi lần đoán, Gấu Po chỉ trả lời "cao hơn", "thấp hơn" hoặc "đúng rồi". Nếu Thỏ đoán lần lượt 1, 2, 3, ... thì có thể mất tới 100 lần. Nhưng nếu Thỏ luôn đoán số ở giữa thì mỗi câu trả lời của Gấu Po loại bỏ đi một nửa các số còn lại. Giả sử Gấu Po nghĩ số 73:

Đoán 50: "cao hơn"  -> còn lại các số 51..100
Đoán 75: "thấp hơn" -> còn lại các số 51..74
Đoán 62: "cao hơn"  -> còn lại các số 63..74
Đoán 68: "cao hơn"  -> còn lại các số 69..74
Đoán 71: "cao hơn"  -> còn lại các số 72..74
Đoán 73: "đúng rồi!"  (chỉ mất 6 lần đoán)

Cách làm này gọi là tìm kiếm nhị phân (binary search): mỗi lần so sánh với phần tử ở giữa rồi bỏ đi một nửa dãy.

Tìm kiếm nhị phân

Điều kiện

Dãy phải được sắp xếp tăng dần. Chỉ khi đó, nhìn phần tử ở giữa ta mới biết số cần tìm nằm ở nửa bên trái hay nửa bên phải. Nếu dãy đang lộn xộn, hãy dùng sort() ở các tuần trước để sắp xếp một lần, rồi mới tìm nhiều lần.

Ý tưởng

Ta giữ một đoạn [l, r] gồm các vị trí mà số x còn có thể nằm trong đó. Mỗi bước lấy mid là vị trí ở giữa đoạn rồi so sánh a[mid] với x:

  • a[mid] = x: tìm thấy x tại vị trí mid, dừng lại.
  • a[mid] < x: x chỉ có thể nằm bên phải, bỏ nửa trái bằng cách đặt l = mid + 1.
  • a[mid] > x: x chỉ có thể nằm bên trái, bỏ nửa phải bằng cách đặt r = mid - 1.

Khi l > r thì đoạn không còn phần tử nào, nghĩa là dãy không có x.

Ví dụ minh họa

Tìm x = 23 trong dãy đã sắp xếp có 10 phần tử:

chỉ số:  0   1   2   3   4   5   6   7   8   9
giá trị: 2   5   8  12  16  23  38  45  56  72

Bước 1: l=0, r=9, mid=4, a[4]=16 < 23  -> bỏ nửa trái,  l = 5
Bước 2: l=5, r=9, mid=7, a[7]=45 > 23  -> bỏ nửa phải,  r = 6
Bước 3: l=5, r=6, mid=5, a[5]=23 = 23  -> tìm thấy ở vị trí 5
Cài đặt
#include <iostream>
#include <vector>
using namespace std;

vector<int> a; // dãy đã sắp xếp tăng dần

// Trả về vị trí của x trong a, hoặc -1 nếu không có
int timNhiPhan(int x) {
    int l = 0, r = (int)a.size() - 1; // đoạn cần tìm là [l, r]
    while (l <= r) {                  // còn ít nhất một phần tử
        int mid = (l + r) / 2;        // vị trí ở giữa
        if (a[mid] == x) return mid;  // trúng rồi
        if (a[mid] < x) l = mid + 1;  // bỏ nửa trái
        else r = mid - 1;             // bỏ nửa phải
    }
    return -1;                        // không có x
}

int main() {
    int n, x;
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> x;
    cout << timNhiPhan(x);
    return 0;
}
Nhị phân nhanh đến mức nào

Mỗi bước làm dãy ngắn đi một nửa, nên số bước chỉ khoảng log2(n) (độ phức tạp O(log n)). Với n = 109, máy tính chỉ cần khoảng 30 bước, nhanh như một cái chớp mắt.

Số phần tử nTuần tự (tối đa) | Nhị phân (tối đa)
1010 phép so sánh | 4 phép so sánh
1 0001 000 phép so sánh | 10 phép so sánh
100 000100 000 phép so sánh | 17 phép so sánh
1 000 000 0001 000 000 000 phép so sánh | 30 phép so sánh
Những lỗi hay gặp
  • Dùng nhị phân trên dãy chưa sắp xếp: kết quả sai mà chương trình vẫn chạy bình thường.
  • Viết l = mid hoặc r = mid thay vì l = mid + 1, r = mid - 1: vòng lặp có thể chạy mãi không dừng.
  • Khi l và r có giá trị rất lớn (ví dụ đoán số đến 109), tổng l + r có thể lên tới 2·109, sát giới hạn của int. Cách viết an toàn hơn là mid = l + (r - l) / 2.

Các hàm có sẵn: binary_search, lower_bound, upper_bound

Thư viện <algorithm> của C++ đã viết sẵn tìm kiếm nhị phân cho ta, chạy trong O(log n). Các hàm này cũng yêu cầu dãy đã sắp xếp tăng dần.

Ý nghĩa
  • lower_bound(x): vị trí của phần tử đầu tiên có giá trị ≥ x.
  • upper_bound(x): vị trí của phần tử đầu tiên có giá trị > x.
  • Nếu không có phần tử nào như vậy, kết quả là vị trí cuối dãy (chỉ số n, đừng đọc a[n]).

Ví dụ với dãy a = {1, 3, 3, 3, 5, 7, 7, 9}:

chỉ số:   0   1   2   3   4   5   6   7   (8)
giá trị:  1   3   3   3   5   7   7   9  (hết)
              L           U
L = lower_bound(3) = 1       U = upper_bound(3) = 4
Số lần xuất hiện của 3:  4 - 1 = 3

lower_bound(4) = 4  (phần tử 5 là số đầu tiên ≥ 4)
upper_bound(4) = 4
lower_bound(10) = 8 = n  (không có số nào ≥ 10)
Cú pháp
#include <iostream>
#include <vector>
#include <algorithm> // thư viện chứa sort, lower_bound, upper_bound
using namespace std;

int main() {
    vector<int> a = {5, 3, 7, 1, 3, 9, 3, 7};
    sort(a.begin(), a.end()); // BẮT BUỘC sắp xếp trước
    int x = 3;
    // trừ a.begin() để đổi từ iterator sang chỉ số
    int i = lower_bound(a.begin(), a.end(), x) - a.begin(); // i = 1
    int j = upper_bound(a.begin(), a.end(), x) - a.begin(); // j = 4
    cout << "Số lần xuất hiện của 3: " << j - i << endl;     // 3
    if (binary_search(a.begin(), a.end(), x)) cout << "Có số 3";
    return 0;
}

Với mảng thường int a[100005] chứa n phần tử (chỉ số từ 0), ta viết: lower_bound(a, a + n, x) - a.

Các hàm
sort()Sắp xếp dãy tăng dần trước khi tìm, mất O(n log n)
binary_search()Trả về true nếu x có trong dãy, ngược lại trả về false
lower_bound()Trả về vị trí phần tử đầu tiên có giá trị lớn hơn hoặc bằng x
upper_bound()Trả về vị trí phần tử đầu tiên có giá trị lớn hơn x
Các công thức hay dùng

Gọi lb = lower_bound(a.begin(), a.end(), x) - a.begin() và ub = upper_bound(a.begin(), a.end(), x) - a.begin(). Dãy a có n phần tử đã sắp xếp.

Cần tìmCách tính
Số phần tử < xlb
Số phần tử ≤ xub
Số phần tử > xn - ub
Số phần tử ≥ xn - lb
Số lần x xuất hiệnub - lb (bằng 0 nếu không có x)
Số phần tử trong đoạn [L, R]ub của R trừ lb của L
Số nhỏ nhất ≥ xa[lb], với điều kiện lb < n
Số lớn nhất ≤ xa[ub - 1], với điều kiện ub > 0
Tự viết lower_bound (không bắt buộc)

Ta có thể tự viết lower_bound bằng nhị phân. Lần này đáp án luôn nằm trong đoạn [l, r] với r = n, và vòng lặp dừng khi l = r:

int l = 0, r = n;               // đáp án nằm trong [0, n]
while (l < r) {
    int mid = (l + r) / 2;
    if (a[mid] < x) l = mid + 1; // đáp án ở bên phải mid
    else r = mid;                // đáp án là mid hoặc bên trái
}
// l chính là vị trí lower_bound(x)

Khi nào dùng cách nào

CáchDùng khi nàoVí dụ
Tìm kiếm tuần tựDãy chưa sắp xếp, chỉ hỏi một vài lầnTìm số đầu tiên chia hết cho 7 trong dãy
Nhị phân tự viếtDãy đã sắp xếp, hỏi rất nhiều lần, hoặc đang chơi trò đoán sốĐoán số của Gấu Po; tìm vị trí của một mã số
lower_bound, upper_boundCần đếm, tìm số gần nhất, hoặc tìm chỗ chènĐếm số bạn có điểm trong một khoảng

Luyện tập

Bài 1. Trò chơi đoán số

Gấu Po nghĩ một số S trong khoảng từ 1 đến N. Thỏ đoán theo cách nhị phân: ban đầu l = 1, r = N. Mỗi lần Thỏ đoán mid = (l + r) / 2. Nếu mid = S thì dừng. Nếu mid < S thì Gấu Po nói "cao hơn" và Thỏ đặt l = mid + 1. Ngược lại Gấu Po nói "thấp hơn" và Thỏ đặt r = mid - 1. Hỏi Thỏ phải đoán bao nhiêu lần?

Đầu vàoMột dòng gồm hai số nguyên N, S (1 ≤ S ≤ N ≤ 109).
Đầu raSố lần Thỏ đoán.
TestInputOutput
1100 736
21000000000 129

Bài 2. Có trong sổ không

Thỏ có cuốn sổ ghi n mã số học sinh đã xếp theo thứ tự tăng dần (không có hai mã trùng nhau). Có q bạn đến hỏi mã số của mình có trong sổ không. Em hãy tự viết tìm kiếm nhị phân để trả lời nhé.

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105).
Dòng 2: n mã số tăng dần (1 ≤ a[i] ≤ 109).
Dòng 3: q mã số cần hỏi (1 ≤ x ≤ 109).
Đầu raq dòng, mỗi dòng in YES nếu có trong sổ, ngược lại in NO.
TestInputOutput
16 3
3 8 15 22 40 91
22 9 91		YES
NO
YES
21 2
5
5 6		YES
NO

Bài 3. Tìm sách trên kệ

Hổ xếp n cuốn sách lên kệ theo mã số tăng dần (không có hai mã trùng nhau). Với mỗi mã số được hỏi, hãy cho biết cuốn sách đó đứng ở vị trí thứ mấy tính từ trái (vị trí đầu tiên là 1).

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105).
Dòng 2: n mã số tăng dần (1 ≤ a[i] ≤ 109).
Dòng 3: q mã số cần hỏi (1 ≤ x ≤ 109).
Đầu raq dòng, mỗi dòng là vị trí của cuốn sách, hoặc -1 nếu trên kệ không có.
TestInputOutput
17 3
4 9 15 21 33 50 72
33 4 10		5
1
-1
23 2
10 20 30
5 30		-1
3

Bài 4. Phiếu bé ngoan

Cô giáo phát cho các bạn n phiếu bé ngoan, mỗi phiếu ghi một số hiệu (số hiệu có thể trùng nhau, các phiếu đang để lộn xộn). Gấu Po hỏi q lần, mỗi lần hỏi có bao nhiêu phiếu mang số hiệu x. Gợi ý: sắp xếp trước, rồi dùng upper_bound trừ lower_bound.

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105).
Dòng 2: n số hiệu (1 ≤ a[i] ≤ 109).
Dòng 3: q số x cần hỏi (1 ≤ x ≤ 109).
Đầu raq dòng, mỗi dòng là số phiếu mang số hiệu x (có thể bằng 0).
TestInputOutput
18 4
5 2 5 9 2 5 7 5
5 2 9 4		4
2
1
0
23 2
7 7 7
7 8		3
0

Bài 5. Bao nhiêu bạn thấp hơn

Cả lớp có n bạn xếp hàng không theo thứ tự chiều cao. Thỏ hỏi q lần, mỗi lần đưa một chiều cao x (đơn vị cm) và muốn biết có bao nhiêu bạn thấp hơn x.

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105).
Dòng 2: n chiều cao (1 ≤ a[i] ≤ 109).
Dòng 3: q giá trị x (1 ≤ x ≤ 109).
Đầu raq dòng, mỗi dòng là số bạn có chiều cao nhỏ hơn x.
TestInputOutput
16 3
140 155 148 160 155 150
155 140 170		3
0
6
24 2
100 100 100 100
100 101		0
4

Bài 6. Thỏ đi mua kẹo

Trong tiệm có n loại kẹo, mỗi loại có một giá tiền. Thỏ có m đồng và muốn mua loại kẹo đắt nhất mà vẫn đủ tiền. Thỏ hỏi q lần với các số tiền m khác nhau. Mỗi lần hãy cho biết giá của loại kẹo đắt nhất mà Thỏ mua được.

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105).
Dòng 2: n giá tiền (1 ≤ a[i] ≤ 109).
Dòng 3: q số tiền m (1 ≤ m ≤ 109).
Đầu raq dòng, mỗi dòng là giá kẹo đắt nhất không vượt quá m, hoặc -1 nếu không mua được loại nào.
TestInputOutput
15 4
12 5 30 8 20
10 4 100 20		8
-1
30
20
23 2
7 7 9
7 8		7
7

Bài 7. Chọn số gần nhất

Hổ có n tấm thẻ ghi số. Với mỗi số x được hỏi, Hổ muốn chọn tấm thẻ có số gần x nhất (gần nhất nghĩa là hiệu giữa hai số, lấy giá trị dương, nhỏ nhất). Nếu có hai thẻ cách đều x thì chọn thẻ có số nhỏ hơn.

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105).
Dòng 2: n số trên thẻ (1 ≤ a[i] ≤ 109).
Dòng 3: q số x (1 ≤ x ≤ 109).
Đầu raq dòng, mỗi dòng là số trên tấm thẻ gần x nhất.
TestInputOutput
15 4
10 20 35 50 80
27 36 5 100		20
35
10
80
22 3
10 20
15 16 14		10
20
10

Bài 8. Điểm trong khoảng

Cô giáo có bảng điểm n bạn. Có q câu hỏi, mỗi câu cho hai số L và R. Em hãy đếm giúp cô có bao nhiêu bạn có điểm từ L đến R (tính cả L và R).

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105).
Dòng 2: n điểm số (1 ≤ a[i] ≤ 109).
q dòng tiếp theo, mỗi dòng hai số L, R (1 ≤ L ≤ R ≤ 109).
Đầu raq dòng, mỗi dòng là số bạn có điểm nằm trong đoạn [L, R].
TestInputOutput
16 3
5 1 9 3 7 3
3 7
10 20
1 9		4
0
6
23 1
4 4 4
4 4		3

Bài 9. Hai chiếc bánh vừa túi

Gấu Po có một chiếc túi chứa vừa đúng K gam. Trên bàn có n chiếc bánh, mỗi chiếc nặng một số gam. Gấu Po muốn chọn đúng hai chiếc bánh ở hai vị trí khác nhau sao cho tổng khối lượng bằng K. Hỏi có chọn được không? Gợi ý: với mỗi bánh nặng v, hãy tìm xem có chiếc bánh nặng K - v hay không. Chú ý trường hợp v + v = K, lúc này phải có ít nhất hai chiếc bánh nặng v.

Đầu vàoDòng 1: hai số nguyên n, K (2 ≤ n ≤ 105; 1 ≤ K ≤ 2·109).
Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109).
Đầu raIn YES nếu có hai vị trí khác nhau i ≠ j mà a[i] + a[j] = K, ngược lại in NO.
TestInputOutput
15 10
5 1 7 3 2		YES
23 8
4 1 2		NO

Bài tập tự luyện

Bài 1. Số lần đoán nhiều nhất

Gấu Po nghĩ một số trong khoảng từ 1 đến N, Thỏ đoán theo cách nhị phân như ở bài "Trò chơi đoán số" ở phần luyện tập. Gấu Po có thể chọn số nào cũng được. Hỏi trong trường hợp xui xẻo nhất, Thỏ phải đoán nhiều nhất bao nhiêu lần?

Đầu vàoMột dòng gồm số nguyên N (1 ≤ N ≤ 109).
Đầu raSố lần đoán nhiều nhất.
TestInputOutput
11007
211

Bài 2. Danh bạ lớp Thỏ

Lớp của Thỏ có n bạn, danh sách tên được xếp theo thứ tự từ điển tăng dần và không có hai tên giống nhau. Có q bạn đến hỏi tên của mình có trong danh sách không. Tên chỉ gồm chữ cái thường, dài không quá 20 ký tự.

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105).
Dòng 2: n tên đã xếp từ điển.
Dòng 3: q tên cần hỏi.
Đầu raq dòng, mỗi dòng in YES nếu tên có trong danh sách, ngược lại in NO.
TestInputOutput
15 3
an binh cuc hoa mai
hoa lan an		YES
NO
YES
22 2
lan mai
mai nam		YES
NO

Bài 3. Bao nhiêu bạn cao hơn

Cả lớp có n bạn với các chiều cao không theo thứ tự. Hổ hỏi q lần, mỗi lần đưa chiều cao x và muốn biết có bao nhiêu bạn cao hơn x (cao hơn hẳn, không tính bằng nhau).

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105).
Dòng 2: n chiều cao (1 ≤ a[i] ≤ 109).
Dòng 3: q giá trị x (1 ≤ x ≤ 109).
Đầu raq dòng, mỗi dòng là số bạn có chiều cao lớn hơn x.
TestInputOutput
15 3
140 150 150 160 170
150 100 170		2
5
0
23 2
10 10 10
9 10		3
0

Bài 4. Chỗ chèn thẻ

Gấu Po có n tấm thẻ đã xếp tăng dần (không có hai số trùng nhau). Gấu Po muốn chèn một thẻ mới mang số x vào đúng chỗ để dãy vẫn tăng dần, nếu đã có thẻ cùng số thì chèn vào ngay trước thẻ đó. Hỏi sau khi chèn, thẻ mới đứng ở vị trí thứ mấy (vị trí đầu tiên là 1)? Có q câu hỏi độc lập, mỗi lần chưa thực sự chèn.

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105).
Dòng 2: n số tăng dần (1 ≤ a[i] ≤ 109).
Dòng 3: q số x (1 ≤ x ≤ 109).
Đầu raq dòng, mỗi dòng là vị trí của thẻ mới sau khi chèn.
TestInputOutput
15 3
10 20 30 40 50
25 5 60		3
1
6
23 2
2 4 6
4 7		2
4

Bài 5. Từ đầu đến cuối

Hổ xếp n viên bi theo số ghi trên bi từ nhỏ đến lớn, có thể có nhiều bi cùng số. Với mỗi số x được hỏi, hãy cho biết các viên bi mang số x đứng liên tiếp từ vị trí nào đến vị trí nào (vị trí đầu tiên là 1).

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105).
Dòng 2: n số không giảm (1 ≤ a[i] ≤ 109).
Dòng 3: q số x (1 ≤ x ≤ 109).
Đầu raq dòng, mỗi dòng gồm hai số: vị trí đầu và vị trí cuối của các viên bi mang số x. Nếu không có viên bi nào thì in -1.
TestInputOutput
18 3
1 3 3 3 5 7 7 9
3 7 4		2 4
6 7
-1
24 2
5 5 5 5
5 6		1 4
-1

Bài 6. Hai dãy gần nhau

Thỏ có n chiếc áo, chiếc thứ i có độ dài tay áo là a[i]. Gấu Po có m chiếc găng tay, chiếc thứ j có độ dài b[j]. Hai bạn muốn chọn một áo và một găng tay sao cho độ dài chênh nhau ít nhất. Hãy tìm độ chênh nhỏ nhất đó (hiệu lấy giá trị dương).

Đầu vàoDòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 105).
Dòng 2: n số a[i] (1 ≤ a[i] ≤ 109).
Dòng 3: m số b[j] (1 ≤ b[j] ≤ 109).
Đầu raĐộ chênh nhỏ nhất.
TestInputOutput
14 3
1 8 20 35
5 14 30		3
22 2
7 9
9 100		0

Bài 7. Cặp cách nhau xa

Hổ có n con số. Hổ muốn đếm xem có bao nhiêu cặp vị trí (i, j) với i < j mà hai số cách nhau ít nhất K, tức là |a[i] - a[j]| ≥ K. Lưu ý kết quả có thể rất lớn, hãy dùng long long.

Đầu vàoDòng 1: hai số nguyên n, K (2 ≤ n ≤ 105; 1 ≤ K ≤ 109).
Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109).
Đầu raSố cặp thỏa mãn.
TestInputOutput
15 4
1 5 3 9 6		5
24 100
1 2 3 4		0

Bài 8. Đếm cặp có tổng K

Gấu Po có n quả cân, mỗi quả nặng một số nguyên gam. Hãy đếm số cặp vị trí (i, j) với i < j mà a[i] + a[j] = K. Gợi ý: sắp xếp rồi với mỗi số v, đếm số lần K - v xuất hiện. Cẩn thận khi v + v = K và khi một cặp bị đếm hai lần.

Đầu vàoDòng 1: hai số nguyên n, K (2 ≤ n ≤ 105; 1 ≤ K ≤ 2·109).
Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109).
Đầu raSố cặp thỏa mãn.
TestInputOutput
16 7
1 6 3 4 2 5		3
24 4
2 2 2 2		6

Bài 9. Thử thách: Dãy xoay vòng (không bắt buộc)

Một dãy gồm n số khác nhau, ban đầu được xếp tăng dần. Sau đó người ta chuyển một số phần tử đầu dãy xuống cuối dãy, ví dụ 10 20 25 30 40 50 60 biến thành 40 50 60 10 20 25 30. Có q câu hỏi, mỗi câu cho số x, hãy cho biết x đứng ở vị trí thứ mấy trong dãy hiện tại (vị trí đầu tiên là 1) hoặc -1 nếu không có. Với n, q lớn, cách duyệt từng số sẽ quá chậm.

Đầu vàoDòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 2·105).
Dòng 2: n số khác nhau của dãy đã bị xoay (1 ≤ a[i] ≤ 109).
Dòng 3: q số x (1 ≤ x ≤ 109).
Đầu raq dòng, mỗi dòng là vị trí của x hoặc -1.
TestInputOutput
17 3
40 50 60 10 20 25 30
25 40 35		6
1
-1
21 2
7
7 8		1
-1
  • Gợi ý chung: Trước khi dùng nhị phân, lower_bound, upper_bound, hãy chắc chắn dãy đã được sắp xếp tăng dần bằng sort. Kết quả của lower_bound, upper_bound là iterator, hãy trừ cho a.begin() để lấy chỉ số, và luôn kiểm tra chỉ số bằng n (không có phần tử phù hợp) trước khi đọc a[chỉ số]. Khi cộng hai số có thể lên tới 2·109 hoặc đếm số cặp, hãy dùng long long để tránh tràn số.