Tìm kiếm nhị phân C++ là kỹ thuật quan trọng khi luyện thi Chuyên Tin: thay vì kiểm tra từng phần tử, ta loại bỏ một phần của dãy sau mỗi bước. Học sinh THCS, THPT tại Kiến An và Hải Phòng nên nắm chắc điều kiện áp dụng và các trường hợp biên trước khi học những bài tìm kiếm trên đáp án.
Điều kiện và ý tưởng
Với dãy đã sắp xếp tăng không giảm, xét phần tử giữa. Nếu nó nhỏ hơn giá trị cần tìm, bỏ nửa trái kể cả phần tử giữa; nếu lớn hơn, bỏ nửa phải. Nếu bằng nhau, ta đã tìm thấy một vị trí. Dãy chưa sắp xếp không đảm bảo thuật toán hoạt động đúng.
Ví dụ dãy 2 4 7 10 13, tìm 10: trước tiên xét 7, bỏ các phần tử không lớn hơn 7, sau đó tìm thấy 10 ở chỉ số 3 tính từ 0.
Cài đặt tìm kiếm nhị phân C++
Nhập n, dãy gồm n số nguyên tăng không giảm và số x. In chỉ số từ 0 của một phần tử bằng x, hoặc -1 nếu không có. Giả định n không âm và vừa trong kiểu int.
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(const vector<int>& a, int x) {
int left = 0;
int right = static_cast<int>(a.size()) - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (a[mid] == x) return mid;
if (a[mid] < x) left = mid + 1;
else right = mid - 1;
}
return -1;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int& value : a) cin >> value;
int x;
cin >> x;
cout << binarySearch(a, x) << endl;
}left và right đều thuộc đoạn đang xét. Khi dãy rỗng, right bằng -1 nên vòng lặp không chạy. Công thức tính mid tránh cộng trực tiếp hai chỉ số lớn. Nếu có các phần tử bằng nhau, kết quả không nhất thiết là vị trí đầu tiên.
Tự kiểm chứng
Lưu mã vào main.cpp, chạy g++ -std=c++17 -Wall -Wextra main.cpp -o main, sau đó chạy ./main. Với đầu vào 5, dãy 2 4 7 10 13 và x = 10, kết quả dự kiến là 3. Thử thêm x = 1, x = 14 và dãy rỗng: kết quả là -1. Với dãy 1 2 2 2 5, tìm 2 có thể trả về chỉ số 1, 2 hoặc 3.
Độ phức tạp và lỗi biên
Mỗi bước loại khoảng một nửa đoạn còn lại: thời gian O(log n), bộ nhớ phụ O(1) không tính mảng đầu vào. Nếu cần sắp xếp trước, phải tính riêng chi phí sắp xếp; chỉ số sau sắp xếp cũng không nhất thiết là chỉ số ban đầu.
- Đừng dùng
left < rightvới đoạn đóng rồi bỏ qua phần tử cuối. - Cập nhật
left = mid + 1hoặcright = mid - 1để đoạn luôn thu nhỏ. - Đừng dừng ở lần bằng nhau đầu tiên nếu đề yêu cầu vị trí xuất hiện đầu tiên.
Tìm vị trí đầu tiên với lower_bound
std::lower_bound trong <algorithm> trả về iterator tới phần tử đầu tiên không nhỏ hơn x trong dãy đã sắp xếp. Nếu không có phần tử phù hợp, kết quả là a.end() và không được dereference.
#include <algorithm>
// a là vector<int> đã sắp xếp; x là giá trị cần tìm
auto it = lower_bound(a.begin(), a.end(), x);
if (it != a.end() && *it == x)
cout << (it - a.begin()) << endl;
else
cout << -1 << endl;Đoạn mã này đặt trong chương trình đã khai báo a, x, cout và các header liên quan. Khi x tồn tại, kết quả là vị trí đầu tiên của nó.
Bài tập luyện thi Chuyên Tin
- Tìm vị trí đầu tiên của
x; kiểm tra dãy có nhiều giá trị trùng nhau và trường hợp không tìm thấy. - Đếm số lần
xxuất hiện bằnglower_boundvàupper_bound. - Tìm phần tử nhỏ nhất không nhỏ hơn
x; xử lý khi iterator bằngend(). - Nâng cao: tìm đáp án nhỏ nhất thỏa điều kiện đơn điệu; trước tiên chứng minh vì sao các đáp án thỏa điều kiện tạo thành một đoạn liên tiếp.
Sau mỗi bài, thử dãy rỗng nếu đề cho phép, một phần tử, giá trị ở hai đầu và giá trị ngoài phạm vi. So sánh kết quả với cách duyệt tuyến tính trên dãy nhỏ để tìm lỗi.
Nguồn tham khảo: C++ reference: lower_bound , upper_bound và sort .
Phụ huynh và học sinh có thể liên hệ VCoderLog Academy để tìm hiểu lớp luyện thi Chuyên Tin C++ và bài kiểm tra thuật toán miễn phí. Phòng Lab tại 261 Phan Đăng Lưu, Kiến An, Hải Phòng; học viên mang laptop cá nhân để thực hành.

