Để bắt đầu đọc bài này, bạn cần biết và sử dụng được kỹ thuật tìm kiếm nhị phân để tìm kiếm một giá trị trên mảng đã được sắp xếp theo thứ tự tăng dần. Nếu bạn chưa biết kỹ thuật này vui lòng thử:
- Đọc qua bài viết về kỹ thuật tìm kiếm nhị phân
- Khám phá qua công cụ minh họa sau (https://yongdanielliang.github.io/animation/web/BinarySearchNew.html).
Trong C++ cũng cung cấp sẵn thuật toán tìm kiếm nhị phân (binary_search) cũng như biến thể của nó là lower_bound & upper_bound. Đây là hai hàm mà nếu biết sử dụng và ứng dụng nó bạn sẽ giải quyết được rất nhiều bài toán cần tìm kiếm một cách tối ưu.
Binary_search
Hàm binary_search() triển khai dựa trên thuật toán tìm kiếm nhị phân, một phương pháp hiệu quả để tìm kiếm một giá trị mục tiêu trong một tập hợp có thứ tự. Hàm này được thiết kế để hoạt động với các cấu trúc dữ liệu có thể sắp xếp như mảng, vector và chuỗi, với điều kiện các phần tử phải được sắp xếp theo thứ tự tăng dần.
Thư viện: “algorithm”
Giá trị trả về : Hàm trả về true nếu giá trị tìm kiếm xuất hiện trong mảng, ngược lại trả về false.
Độ phức tạp : O(logN)
Cú pháp:
//Cú pháp áp dụng với mảng a[] gồm n phần tử và giá trị tìm kiếm x binary_search(a, a + n, x) //Cú pháp áp dụng với vector, string và giá trị tìm kiếm x (kiểu dữ liệu của x tương đồng với kiểu dữ liệu của phần tử trong vector hoặc string) binary_search(v.begin(), v.end(), x) binary_search(s.begin(), s.end(), x)
Chương trình minh họa:
/**
* Chương trình minh họa việc sử dụng hàm binary_search() trong thư viện algorithm của C++
* để tìm kiếm phần tử trong mảng và vector đã được sắp xếp.
*/
#include <iostream> // Thư viện cho các hàm nhập/xuất cơ bản
#include <algorithm> // Thư viện chứa hàm binary_search() và nhiều thuật toán khác
using namespace std;
int main() {
// Khởi tạo mảng 10 phần tử đã được sắp xếp tăng dần
int a[10] = {1, 2, 3, 5, 5, 6, 8, 9, 14, 21};
int n = 10; // Kích thước của mảng
int X = 5; // Giá trị cần tìm kiếm
// Tìm kiếm giá trị X trong mảng a sử dụng binary_search()
// Tham số: a là điểm bắt đầu, a + n là điểm kết thúc (không bao gồm), X là giá trị cần tìm
if (binary_search(a, a + n, X)) {
cout << "FOUND\n"; // In ra kết quả nếu tìm thấy X
}
else {
cout << "NOT FOUND\n"; // In ra kết quả nếu không tìm thấy X
}
// Khởi tạo vector với các phần tử đã được sắp xếp tăng dần
vector<int> v = {1, 2, 3, 4, 5, 6, 6, 6, 8, 9};
// Tìm kiếm giá trị X trong vector v sử dụng binary_search()
// Tham số:
// v.begin() là iterator đầu tiên,
// v.end() là iterator sau phần tử cuối cùng,
// X là giá trị cần tìm
if (binary_search(v.begin(), v.end(), X)) {
cout << "FOUND\n"; // In ra kết quả nếu tìm thấy X
}
else {
cout << "NOT FOUND\n"; // In ra kết quả nếu không tìm thấy X
}
return 0; // Kết thúc chương trình
}
Giới hạn đoạn cần tìm kiếm trong khoảng từ L đến R
Ngoài ra bạn cũng có thể tìm kiếm trên đoạn chỉ số [L, R] của mảng hoặc vector
Cú pháp:
//Cú pháp áp dụng với mảng a[] binary_search(a + L, a + R + 1, x) //Cú pháp áp dụng với vector binary_search(v.begin() + L, v.begin() + R + 1, x)
Minh họa trên vector:
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int a[10] = {1, 2, 3, 5, 5, 6, 8, 9, 14, 21};
int n = 10, X = 5;
if(binary_search(a + 5, a + 8, X)){
cout << "FOUND\n";
}
else{
cout << "NOT FOUND\n";
}
vector<int> v = {1, 2, 3, 4, 5, 6, 6, 6, 8, 9};
if(binary_search(v.begin() + 2, v.begin() + 7, X)){
cout << "FOUND\n";
}
else{
cout << "NOT FOUND\n";
}
}
lower_bound
Hàm lower_bound() được dùng để tìm vị trí của giá trị nhỏ nhất lớn hơn hoặc bằng giá trị X $(X \le )$ mà bạn tìm kiếm trong mảng hoặc vector tăng dần, ngoài ra nó còn có thể áp dụng với set & map.
Hàm này tương đối khó dùng vì nó cần bạn thành thạo kiến thức về con trỏ và iterator.
Giá trị trả về :
Đối với mảng, hàm này trả về con trỏ tới vị trí có giá trị nhỏ nhất ≥ giá trị tìm kiếm.
- Nếu không tìm thấy, hàm trả về
a + n(tức là ngay sau phần tử cuối cùng của mảng).
- Trường hợp đặc biệt:
- Nếu giá trị cần tìm > phần tử lớn nhất của mảng, con trỏ trả về sẽ là
a + n. - Nếu giá trị cần tìm < phần tử nhỏ nhất của mảng, con trỏ trả về sẽ là
a, tức là phần tử đầu tiên của mảng.
- Nếu giá trị cần tìm > phần tử lớn nhất của mảng, con trỏ trả về sẽ là
Đối với vector, hàm trả về iterator tới vị trí có giá trị nhỏ nhất ≥ giá trị tìm kiếm.
- Nếu không tìm thấy, hàm trả về
vector.end(). - Trường hợp đặc biệt:
- Nếu giá trị cần tìm lớn hơn phần tử lớn nhất của vector, iterator trả về sẽ là
vector.end(). - Nếu giá trị cần tìm nhỏ hơn phần tử nhỏ nhất của vector, iterator trả về sẽ là
vector.begin().
- Nếu giá trị cần tìm lớn hơn phần tử lớn nhất của vector, iterator trả về sẽ là
Độ phức tạp : O(logN)
Cú pháp
//Cú pháp áp dụng trên mảng a[] gồm n phần tử và giá trị tìm kiếm X lower_bound(a, a + n, X) //Cú pháp áp dụng trên vector và giá trị tìm kiếm X lower_bound(v.begin(), v.end(), X)
Iterator trong C++ là một đối tượng tương tự như con trỏ, nó được sử dụng trỏ đến các phần tử trong các cấu trúc như vector, set, map… (Tham khảo thêm)
Minh họa trên vector
/**
* Chương trình minh họa việc sử dụng hàm lower_bound() trong thư viện algorithm của C++
* để tìm phần tử đầu tiên có giá trị lớn hơn hoặc bằng một giá trị cho trước trong một container đã sắp xếp.
*/
#include <iostream> // Thư viện cho các hàm nhập/xuất cơ bản
#include <algorithm> // Thư viện chứa hàm lower_bound() và nhiều thuật toán khác
using namespace std;
int main() {
// Khởi tạo vector với các phần tử đã được sắp xếp tăng dần
vector<int> v = {1, 2, 3, 5, 5, 5, 8, 9, 14, 21};
int X = 5; // Giá trị thứ nhất cần tìm
int Y = 22; // Giá trị thứ hai cần tìm
//lower_bound() để xác định iterator đến phần tử đầu tiên có giá trị KHÔNG NHỎ HƠN (X<=)
vector<int>::iterator it1 = lower_bound(v.begin(), v.end(), X);
// Kiểm tra nếu không tìm thấy phần tử nào >= X
// Nếu iterator bằng v.end() nghĩa là không tìm thấy phần tử nào thỏa mãn
if (it1 == v.end()) {
cout << "Khong tim duoc gia tri >= 5" << endl;
}
else {
// In ra giá trị tìm được bằng cách dereference iterator (*it1)
cout << "Gia tri nho nhat >= 5 : " << *it1 << endl;
// Tính chỉ số của phần tử tìm được bằng cách trừ iterator ban đầu
// Phép trừ hai iterator trả về khoảng cách giữa chúng
cout << "Chi so cua gia tri tim duoc : " << it1 - v.begin() << endl;
}
// Sử dụng lower_bound() để tìm iterator đến phần tử đầu tiên có giá trị >= Y (22)
vector<int>::iterator it2 = lower_bound(v.begin(), v.end(), Y);
// Kiểm tra nếu không tìm thấy phần tử nào >= Y
if (it2 == v.end()) {
cout << "Khong tim duoc gia tri >= 22" << endl;
}
else {
cout << "Gia tri nho nhat >= 22 : " << *it2 << endl;
cout << "Chi so cua gia tri tim duoc : " << it2 - v.begin() << endl;
}
return 0; // Kết thúc chương trình
}
Minh họa trên mảng
/**
* Chương trình minh họa việc sử dụng hàm lower_bound() trong thư viện algorithm của C++
* để xác định vị trí của phần tử đầu tiên có giá trị lớn hơn hoặc bằng một giá trị cho trước trong một mảng đã sắp xếp.
*/
#include <iostream> // Thư viện cho các hàm nhập/xuất cơ bản
#include <algorithm> // Thư viện chứa hàm lower_bound() và nhiều thuật toán khác
using namespace std;
int main() {
// Khởi tạo mảng với các phần tử đã được sắp xếp tăng dần
int a[10] = {1, 2, 3, 5, 5, 5, 8, 9, 14, 21};
int n = 10; // Kích thước của mảng
int X = 5; // Giá trị thứ nhất cần tìm
int Y = 22; // Giá trị thứ hai cần tìm
// Sử dụng lower_bound() để xác định vị trí của phần tử đầu tiên có giá trị >= X (5)
// Tham số: a là điểm bắt đầu, a + n là điểm kết thúc (không bao gồm), X là giá trị cần tìm
int *it1 = lower_bound(a, a + n, X);
// Kiểm tra nếu không tìm thấy phần tử nào >= X
// Nếu con trỏ bằng a + n nghĩa là không tìm thấy phần tử nào thỏa mãn
if (it1 == a + n) {
cout << "Khong tim duoc gia tri >= 5" << endl;
}
else {
// In ra giá trị tìm được bằng cách dereference con trỏ (*it1)
cout << "Gia tri nho nhat >= 5 : " << *it1 << endl;
// Tính chỉ số của phần tử tìm được bằng cách trừ địa chỉ ban đầu
// Phép trừ hai con trỏ trả về khoảng cách giữa chúng
cout << "Chi so cua gia tri tim duoc : " << it1 - a << endl;
}
// Sử dụng lower_bound() để tìm con trỏ đến phần tử đầu tiên có giá trị >= Y (22)
int *it2 = lower_bound(a, a + n, Y);
// Kiểm tra nếu không tìm thấy phần tử nào >= Y
if (it2 == a + n) {
cout << "Khong tim duoc gia tri >= 22" << endl;
}
else {
cout << "Gia tri nho nhat >= 22 : " << *it2 << endl;
cout << "Chi so cua gia tri tim duoc : " << it2 - a << endl;
}
return 0; // Kết thúc chương trình
}
Chú ý : Bạn cũng có thể áp dụng hàm lower_bound trên đoạn chỉ số [L, R], cú pháp tương tự như hàm binary_search
upper_bound
Hàm upper_bound() cách dùng, cú pháp, giá trị trả về, độ phức tạp đều giống hàm lower_bound chỉ khác duy nhất là hàm này tìm vị trí của giá trị nhỏ nhất lớn hơn giá trị X $(X < )$ mà bạn tìm kiếm trong mảng tăng dần.
Cú pháp:
//Cú pháp áp dụng trên mảng a[] gồm n phần tử và giá trị tìm kiếm X upper_bound(a, a + n, X) //Cú pháp áp dụng trên vector và giá trị tìm kiếm X upper_bound(v.begin(), v.end(), X)
Minh họa trên vector
/**
* Chương trình minh họa việc sử dụng hàm upper_bound() và lower_bound() trong thư viện algorithm của C++
* upper_bound() - tìm phần tử đầu tiên có giá trị lớn hơn một giá trị cho trước
* lower_bound() - tìm phần tử đầu tiên có giá trị lớn hơn hoặc bằng một giá trị cho trước
*/
#include <iostream> // Thư viện cho các hàm nhập/xuất cơ bản
#include <algorithm> // Thư viện chứa hàm upper_bound(), lower_bound() và nhiều thuật toán khác
using namespace std;
int main() {
// Khởi tạo vector với các phần tử đã được sắp xếp tăng dần
vector<int> v = {1, 2, 3, 5, 5, 5, 8, 9, 14, 21};
int X = 5; // Giá trị thứ nhất cần tìm
int Y = 22; // Giá trị thứ hai cần tìm
// Sử dụng upper_bound() để tìm iterator đến phần tử đầu tiên có giá trị > X (5)
// Khác với lower_bound(), upper_bound() tìm phần tử đầu tiên lớn hơn X (không bao gồm bằng)
vector<int>::iterator it1 = upper_bound(v.begin(), v.end(), X);
// Kiểm tra nếu không tìm thấy phần tử nào > X
// Nếu iterator bằng v.end() nghĩa là không tìm thấy phần tử nào thỏa mãn
if (it1 == v.end()) {
cout << "Khong tim duoc gia tri > 5" << endl;
}
else {
// In ra giá trị tìm được bằng cách dereference iterator (*it1)
cout << "Gia tri nho nhat > 5 : " << *it1 << endl;
// Tính chỉ số của phần tử tìm được bằng cách trừ iterator ban đầu
cout << "Chi so cua gia tri tim duoc : " << it1 - v.begin() << endl;
}
// Sử dụng lower_bound() để tìm iterator đến phần tử đầu tiên có giá trị >= Y (22)
// Chú ý: Mã nguồn sử dụng lower_bound() nhưng thông báo kết quả là "Không tìm được giá trị > 22"
// Điều này có thể gây hiểu lầm vì lower_bound() thực sự tìm giá trị >= Y
vector<int>::iterator it2 = lower_bound(v.begin(), v.end(), Y);
// Kiểm tra nếu không tìm thấy phần tử nào >= Y
if (it2 == v.end()) {
cout << "Khong tim duoc gia tri > 22" << endl; // Chú ý: Thông báo này không chính xác
}
else {
cout << "Gia tri nho nhat > 22 : " << *it2 << endl; // Chú ý: Thông báo này không chính xác
cout << "Chi so cua gia tri tim duoc : " << it2 - v.begin() << endl;
}
return 0; // Kết thúc chương trình
}
Minh họa trên mảng
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int a[10] = {1, 2, 3, 5, 5, 5, 8, 9, 14, 21};
int n = 10, X = 5, Y = 22;
int *it1 = upper_bound(a, a + n, X);
if(it1 == a + n){
cout << "Khong tim duoc gia tri > 5" << endl;
}
else{
cout << "Gia tri nho nhat > 5 : " << *it1 << endl;
cout << "Chi so cua gia tri tim duoc : " << it1 - a << endl;
}
int *it2 = upper_bound(a, a + n, Y);
if(it2 == a + n){
cout << "Khong tim duoc gia tri > 22" << endl;
}
else{
cout << "Gia tri nho nhat > 22 : " << *it2 << endl;
cout << "Chi so cua gia tri tim duoc : " << it2 - a << endl;
}
}
Cách sử dụng lower_bound và upper_bound trên tập V:
Phần tử X cần tìm xuất hiện trong V:
Lúc này lower_bound và upper_bound trả về 2 vị trí mà từ đó ta có thể biết được số lần xuất hiện của X trong V.
Phần tử X cần tìm KHÔNG xuất hiện trong V:
Lúc này lower_bound và upper_bound chỉ vào cùng vị trí.
Nguồn tham khảo: 28tech.com.vn