Bài 16: Tìm kiếm nhị phân trong C++ và Python: lower_bound, upper_bound và kỹ thuật chặt nhị phân đáp án
Lời mở đầu
Trò chơi quen thuộc: thầy nghĩ một số từ 1 tới 100, em đoán, thầy chỉ trả lời “lớn hơn” hoặc “nhỏ hơn”. Cách chơi thông minh nhất là luôn đoán số ở giữa: đoán 50, nếu “nhỏ hơn” thì số cần tìm nằm trong 1 – 49, đoán tiếp 25… Mỗi lần đoán loại đi một nửa, nên chỉ cần tối đa 7 lần cho 100 số và 20 lần cho một triệu số. Ý tưởng đơn giản này gọi là tìm kiếm nhị phân (binary search).
Ở bài 6 em đã gặp tìm kiếm nhị phân trên mảng. Bài này đi sâu hơn: cách viết không bao giờ sai, các hàm lower_bound, upper_bound, và đặc biệt là kỹ thuật chặt nhị phân đáp án, biến rất nhiều bài “tìm giá trị lớn nhất / nhỏ nhất” khó nhằn thành bài “kiểm tra có làm được không” dễ hơn nhiều.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Ý tưởng: mỗi bước loại bỏ một nửa
Tìm kiếm tuần tự xét lần lượt từng phần tử, tốn $O(n)$. Tìm kiếm nhị phân chỉ dùng được khi dữ liệu có thứ tự (ví dụ mảng đã sắp xếp tăng dần), nhưng đổi lại cực nhanh: sau mỗi bước, vùng cần tìm giảm một nửa: $n \to \frac{n}{2} \to \frac{n}{4} \to \dots \to 1$. Số bước là số lần chia đôi $n$ cho tới khi còn 1, tức khoảng $\log_2 n$.
| Số phần tử $n$ | 10 | 1000 | $10^6$ | $10^9$ | $10^{18}$ |
|---|---|---|---|---|---|
| Tìm tuần tự (bước) | 10 | 1000 | $10^6$ | $10^9$ | $10^{18}$ |
| Tìm nhị phân (bước) | 4 | 10 | 20 | 30 | 60 |
Mô phỏng trực quan. "Mỗi bước loại một nửa" nghe đơn giản nhưng sức mạnh của nó chỉ thấy rõ khi em tận mắt nhìn khoảng tìm kiếm co lại. Em chơi trò đoán số dưới đây, rồi thử tăng N lên một tỷ để thấy số lần đoán chỉ nhích thêm vài lần.
Phần 2Tìm kiếm nhị phân trên mảng đã sắp xếp
Ta giữ hai đầu l, r của vùng còn khả năng chứa $x$. Mỗi bước xét phần tử chính giữa mid = (l + r) / 2: nếu a[mid] == x thì tìm thấy; nếu a[mid] < x thì mọi phần tử từ l tới mid đều nhỏ hơn $x$ (mảng tăng), bỏ chúng đi: l = mid + 1; ngược lại bỏ nửa phải: r = mid - 1. Khi l > r vùng tìm rỗng, tức không có $x$.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, x;
cin >> n;
vector<int> a(n);
for(int &v : a) cin >> v;
cin >> x;
int l = 0, r = n - 1, kq = -1;
while(l <= r){
int mid = (l + r) / 2;
if(a[mid] == x){ kq = mid; break; }
else if(a[mid] < x) l = mid + 1;
else r = mid - 1;
}
cout << kq;
return 0;
}n = int(input())
a = list(map(int, input().split()))
x = int(input())
l, r, kq = 0, n - 1, -1
while l <= r:
mid = (l + r) // 2
if a[mid] == x:
kq = mid
break
elif a[mid] < x:
l = mid + 1
else:
r = mid - 1
print(kq)Phần 3Khuôn mẫu vạn năng: tìm vị trí đầu tiên thỏa điều kiện
Rất nhiều câu hỏi không phải “có $x$ không” mà là: phần tử đầu tiên $\ge x$ ở đâu? (để chèn $x$ vào mà mảng vẫn tăng), có bao nhiêu số $< x$?, $x$ xuất hiện bao nhiêu lần? Tất cả quy về một khuôn mẫu: với điều kiện dk(i) có tính đơn điệu, nghĩa là sai ở đầu mảng rồi đúng mãi về sau (false false … false true true … true), hãy tìm vị trí true đầu tiên.
Cách viết dưới đây giữ kq là đáp án tốt nhất tìm được: gặp mid thỏa điều kiện thì ghi nhận rồi tìm tiếp sang trái xem có vị trí nhỏ hơn không; không thỏa thì sang phải. Cách này không bao giờ lặp vô hạn và rất dễ đổi cho bài khác: chỉ cần thay điều kiện.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, x;
cin >> n;
vector<int> a(n);
for(int &v : a) cin >> v;
cin >> x;
int l = 0, r = n - 1, kq = n;
while(l <= r){
int mid = (l + r) / 2;
if(a[mid] >= x){
kq = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << kq;
return 0;
}n = int(input())
a = list(map(int, input().split()))
x = int(input())
l, r, kq = 0, n - 1, n
while l <= r:
mid = (l + r) // 2
if a[mid] >= x:
kq = mid
r = mid - 1
else:
l = mid + 1
print(kq) # giống bisect.bisect_left(a, x)lower_bound(a.begin(), a.end(), x) - a.begin(): vị trí đầu tiên có giá trị ≥ x.upper_bound(a.begin(), a.end(), x) - a.begin(): vị trí đầu tiên có giá trị > x.- Số lần xuất hiện của $x$:
upper_bound(...) - lower_bound(...). Số phần tử thuộc đoạn $[u, v]$:upper_bound(v) - lower_bound(u). binary_search(a.begin(), a.end(), x): trả vềtrue/falsecó $x$ hay không.
from bisect import bisect_left, bisect_right, dùng giống hệt lower_bound và upper_bound. Với set hay map của C++ (bài 11) thì gọi s.lower_bound(x), không dùng hàm chung (sẽ chạy $O(n)$).Mô phỏng trực quan. Khuôn mẫu "vị trí đầu tiên thỏa điều kiện" dễ nhầm nhất ở hai chỗ: khi nào gán ans và vì sao lại r = mid − 1. Em xem hàng Đ/S bên dưới được "lật" dần từng ô, và để ý ta không bao giờ phải nhìn hết cả mảng.
Phần 4Chặt nhị phân đáp án
Đây là phần đáng giá nhất của bài. Xét bài Cắt gỗ: có $n$ khúc gỗ dài $a_1, \dots, a_n$, cần cắt ra ít nhất $k$ đoạn có cùng độ dài $L$ (nguyên dương, phần thừa bỏ đi). Hỏi $L$ lớn nhất là bao nhiêu?
Tìm thẳng $L$ tối ưu thì khó. Nhưng câu hỏi ngược lại rất dễ: “nếu cắt mỗi đoạn dài $L$ thì được bao nhiêu đoạn?” Đáp: $\sum \lfloor a_i / L \rfloor$, tính trong $O(n)$. Và hàm này đơn điệu: $L$ càng lớn thì càng được ít đoạn. Vậy điều kiện ok(L) = “cắt được ít nhất $k$ đoạn” đúng với $L$ nhỏ và sai từ một ngưỡng trở đi (true … true false … false). Ta cần true cuối cùng, tìm bằng đúng khuôn mẫu ở phần 3, chỉ đổi chiều. Độ phức tạp $O(n \log(\max a))$.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int n;
long long k, a[100005];
long long soDoan(long long L){
long long s = 0;
for(int i = 0; i < n; i++) s += a[i] / L;
return s;
}
int main(){
cin >> n >> k;
for(int i = 0; i < n; i++) cin >> a[i];
long long l = 1, r = *max_element(a, a + n), kq = 0;
while(l <= r){
long long mid = (l + r) / 2;
if(soDoan(mid) >= k){
kq = mid;
l = mid + 1;
}
else r = mid - 1;
}
cout << kq;
return 0;
}n, k = map(int, input().split())
a = list(map(int, input().split()))
def so_doan(L):
return sum(x // L for x in a)
l, r, kq = 1, max(a), 0
while l <= r:
mid = (l + r) // 2
if so_doan(mid) >= k:
kq = mid # cắt được → thử dài hơn
l = mid + 1
else:
r = mid - 1
print(kq)Xem chặt nhị phân trên trục số: mỗi bước tô xanh phần đáp án đã chắc chắn làm được, đỏ phần chắc chắn không làm được; vùng tím ở giữa là vùng còn phải tìm và co lại một nửa sau mỗi lần đoán.
Phần 5Tìm nhị phân trên số thực và các lỗi hay gặp
Khi đáp án là số thực (ví dụ tìm $x$ để $x^3 + x = 10$, hay độ dài cắt không cần nguyên), không có “$mid + 1$” nữa. Cách an toàn nhất là lặp một số lần cố định, mỗi lần vùng tìm giảm một nửa: sau 100 lần, độ rộng chỉ còn $\frac{1}{2^{100}}$ ban đầu, chính xác hơn mọi yêu cầu.
Tìm nghiệm phương trình bằng chia đôi
#include <bits/stdc++.h>
using namespace std;
int main(){
double c;
cin >> c; // tìm x ≥ 0 với x^3 + x = c (c ≥ 0)
double l = 0, r = max(1.0, c);
for(int lan = 0; lan < 100; lan++){
double mid = (l + r) / 2;
if(mid * mid * mid + mid < c) l = mid; // còn nhỏ quá → bên phải
else r = mid;
}
cout << fixed << setprecision(6) << l;
return 0;
}c = float(input())
l, r = 0.0, max(1.0, c)
for _ in range(100):
mid = (l + r) / 2
if mid ** 3 + mid < c:
l = mid
else:
r = mid
print(f"{l:.6f}")sort trước.2. Lặp vô hạn: viết
while(l < r) với l = mid dễ bị kẹt khi r = l + 1 (mid luôn bằng l). Dùng khuôn mẫu while(l <= r) + biến kq như bài này để không bao giờ phải lo.3. Tràn số:
l + r với int gần $2 \cdot 10^9$ bị tràn; dùng long long (hoặc l + (r - l) / 2). Hàm kiểm tra cũng có thể tràn: với $mid \approx 10^{18}$, phép mid * mid vượt long long, hãy so sánh mid <= n / mid thay cho mid * mid <= n.4. Chọn sai cận: cận phải bao trùm đáp án. Với bài “nhỏ nhất”, nếu cận trên quá nhỏ thì kq không được cập nhật lần nào.
- Cắt Dây (CATDAY) (Trung bình)
- Factory Machines (CSES 1620) (Trung bình)
- Chia Đoạn (SEG) (Trung bình)
- Tìm kiếm nhị phân 3 (SEARCH3) (Trung bình)
- Trúc (2023HITOPENDAY_3) (Trung bình)
Bài tậpLuyện tìm kiếm nhị phân
Cho mảng $n$ số nguyên tăng ngặt ($n \le 10^5$) và $q$ truy vấn ($q \le 10^5$). Mỗi truy vấn là một số $x$: in vị trí (đánh số từ 1) của $x$ trong mảng, hoặc $-1$ nếu không có.
5
1 4 7 9 12
3
7 1 83
1
-1💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n;
vector<int> a(n);
for(int &v : a) cin >> v;
cin >> q;
while(q--){
int x; cin >> x;
int p = lower_bound(a.begin(), a.end(), x) - a.begin();
if(p < n && a[p] == x) cout << p + 1 << "\n";
else cout << -1 << "\n";
}
return 0;
}import sys
from bisect import bisect_left
data = sys.stdin.read().split()
n = int(data[0]); a = list(map(int, data[1:n + 1]))
q = int(data[n + 1]); out = []
for x in map(int, data[n + 2:n + 2 + q]):
p = bisect_left(a, x)
out.append(str(p + 1) if p < n and a[p] == x else "-1")
print('\n'.join(out))Cho $n$ số nguyên ($n \le 10^5$, chưa sắp xếp) và $q$ truy vấn $x$. Với mỗi truy vấn, in số lần $x$ xuất hiện.
8
5 1 5 3 9 5 1 7
3
5 1 43
2
0💡 Gợi ý
upper_bound - lower_bound. (Dùng map đếm cũng được, nhưng bài 3 sẽ cần đúng kỹ thuật này.)Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n;
vector<int> a(n);
for(int &v : a) cin >> v;
sort(a.begin(), a.end());
cin >> q;
while(q--){
int x; cin >> x;
cout << upper_bound(a.begin(), a.end(), x) - lower_bound(a.begin(), a.end(), x) << "\n";
}
return 0;
}import sys
from bisect import bisect_left, bisect_right
data = sys.stdin.read().split()
n = int(data[0]); a = sorted(map(int, data[1:n + 1]))
q = int(data[n + 1])
print('\n'.join(str(bisect_right(a, x) - bisect_left(a, x)) for x in map(int, data[n + 2:n + 2 + q])))Cho $n$ số nguyên và $q$ truy vấn, mỗi truy vấn gồm hai số $u \le v$: đếm số phần tử có giá trị thuộc đoạn $[u, v]$.
6
7 2 9 4 4 12
3
3 8
1 100
10 113
6
0💡 Gợi ý
lower_bound(u) tới trước upper_bound(v). Đáp án là hiệu hai vị trí.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, q;
cin >> n;
vector<long long> a(n);
for(auto &v : a) cin >> v;
sort(a.begin(), a.end());
cin >> q;
while(q--){
long long u, v; cin >> u >> v;
cout << upper_bound(a.begin(), a.end(), v) - lower_bound(a.begin(), a.end(), u) << "\n";
}
return 0;
}import sys
from bisect import bisect_left, bisect_right
data = sys.stdin.read().split()
n = int(data[0]); a = sorted(map(int, data[1:n + 1]))
q = int(data[n + 1]); out = []
for t in range(q):
u, v = int(data[n + 2 + 2 * t]), int(data[n + 3 + 2 * t])
out.append(str(bisect_right(a, v) - bisect_left(a, u)))
print('\n'.join(out))Cho $n$ ($0 \le n \le 10^{18}$). In số nguyên $x$ lớn nhất thỏa $x^2 \le n$.
10000000000000000001000000000💡 Gợi ý
sqrt của số thực có thể sai ở hàng đơn vị với số lớn cỡ $10^{18}$. Chặt nhị phân $x$ trong $[0, 2 \cdot 10^9]$; để tránh tràn khi tính $x^2$, kiểm tra x <= n / x (với $x > 0$) thay cho x * x <= n. Python có math.isqrt.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin >> n;
long long l = 1, r = 2000000000LL, kq = 0;
while(l <= r){
long long mid = (l + r) / 2;
if(mid <= n / mid){ kq = mid; l = mid + 1; }
else r = mid - 1;
}
cout << kq;
return 0;
}import math
print(math.isqrt(int(input())))Có $n$ khúc gỗ ($n \le 10^5$, độ dài $\le 10^9$). Tìm độ dài nguyên $L$ lớn nhất để cắt được ít nhất $k$ đoạn ($k \le 10^9$) dài đúng $L$. Nếu không cắt nổi, in 0.
4 11
802 743 457 539200💡 Gợi ý
long long vì tổng có thể tới $10^{14}$).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; long long k;
cin >> n >> k;
vector<long long> a(n);
for(auto &v : a) cin >> v;
long long l = 1, r = *max_element(a.begin(), a.end()), kq = 0;
while(l <= r){
long long mid = (l + r) / 2, s = 0;
for(long long v : a) s += v / mid;
if(s >= k){ kq = mid; l = mid + 1; }
else r = mid - 1;
}
cout << kq;
return 0;
}n, k = map(int, input().split())
a = list(map(int, input().split()))
l, r, kq = 1, max(a), 0
while l <= r:
mid = (l + r) // 2
if sum(v // mid for v in a) >= k:
kq, l = mid, mid + 1
else:
r = mid - 1
print(kq)Nhà máy có $n$ máy, máy thứ $i$ làm xong một sản phẩm sau $t_i$ giây, các máy chạy song song. Hỏi thời gian ít nhất để làm được $m$ sản phẩm ($n \le 2 \cdot 10^5$, $t_i, m \le 10^9$).
3 7
3 2 58💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; long long m;
cin >> n >> m;
vector<long long> t(n);
for(auto &v : t) cin >> v;
long long l = 1, r = *min_element(t.begin(), t.end()) * m, kq = r;
while(l <= r){
long long mid = l + (r - l) / 2, s = 0;
for(long long v : t){ s += mid / v; if(s >= m) break; }
if(s >= m){ kq = mid; r = mid - 1; }
else l = mid + 1;
}
cout << kq;
return 0;
}n, m = map(int, input().split())
t = list(map(int, input().split()))
l, r = 1, min(t) * m
kq = r
while l <= r:
mid = (l + r) // 2
if sum(mid // v for v in t) >= m:
kq, r = mid, mid - 1
else:
l = mid + 1
print(kq)Chia dãy $n$ số nguyên dương ($n \le 10^5$, $a_i \le 10^9$) thành đúng $k$ đoạn liên tiếp khác rỗng ($k \le n$) sao cho tổng lớn nhất trong các đoạn là nhỏ nhất. In giá trị đó.
5 2
7 2 5 10 818💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<long long> a;
bool ok(long long X){
int doan = 1; long long s = 0;
for(long long v : a){
if(s + v > X){ doan++; s = v; }
else s += v;
}
return doan <= k;
}
int main(){
cin >> n >> k;
a.resize(n);
for(auto &v : a) cin >> v;
long long l = *max_element(a.begin(), a.end()), r = accumulate(a.begin(), a.end(), 0LL), kq = r;
while(l <= r){
long long mid = (l + r) / 2;
if(ok(mid)){ kq = mid; r = mid - 1; }
else l = mid + 1;
}
cout << kq;
return 0;
}n, k = map(int, input().split())
a = list(map(int, input().split()))
def ok(X):
doan, s = 1, 0
for v in a:
if s + v > X:
doan += 1
s = v
else:
s += v
return doan <= k
l, r = max(a), sum(a)
kq = r
while l <= r:
mid = (l + r) // 2
if ok(mid):
kq, r = mid, mid - 1
else:
l = mid + 1
print(kq)Có $n$ chuồng ở các vị trí $x_1, \dots, x_n$ trên một đường thẳng ($n \le 10^5$, $x_i \le 10^9$). Xếp $c$ con bò ($2 \le c \le n$) vào $c$ chuồng khác nhau sao cho khoảng cách nhỏ nhất giữa hai con bò là lớn nhất. In khoảng cách đó.
5 3
1 2 8 4 93💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int n, c;
vector<long long> x;
bool ok(long long D){
int dat = 1; long long cuoi = x[0];
for(int i = 1; i < n; i++)
if(x[i] - cuoi >= D){ dat++; cuoi = x[i]; }
return dat >= c;
}
int main(){
cin >> n >> c;
x.resize(n);
for(auto &v : x) cin >> v;
sort(x.begin(), x.end());
long long l = 1, r = x[n - 1] - x[0], kq = 0;
while(l <= r){
long long mid = (l + r) / 2;
if(ok(mid)){ kq = mid; l = mid + 1; }
else r = mid - 1;
}
cout << kq;
return 0;
}n, c = map(int, input().split())
x = sorted(map(int, input().split()))
def ok(D):
dat, cuoi = 1, x[0]
for v in x[1:]:
if v - cuoi >= D:
dat += 1
cuoi = v
return dat >= c
l, r, kq = 1, x[-1] - x[0], 0
while l <= r:
mid = (l + r) // 2
if ok(mid):
kq, l = mid, mid + 1
else:
r = mid - 1
print(kq)
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét