Bài 23.4: Bài tập thực hành tìm kiếm nâng cao trong C++

Chào mừng quay trở lại với chuỗi bài blog về C++! Sau khi đã nắm vững các khái niệm cơ bản và các cấu trúc dữ liệu quen thuộc, chúng ta sẽ cùng nhau đi sâu vào một chủ đề cực kỳ quan trọng trong lập trình: Tìm kiếm.

Tìm kiếm là một thao tác cơ bản và thiết yếu. Tuy nhiên, không phải lúc nào việc tìm kiếm cũng chỉ đơn giản là duyệt qua từng phần tử từ đầu đến cuối. Đối với các tập dữ liệu lớn hoặc khi cần tìm kiếm theo các tiêu chí phức tạp, chúng ta cần đến các kỹ thuật và thuật toán tìm kiếm nâng cao. C++ Standard Library (STL) cung cấp một bộ công cụ mạnh mẽ giúp chúng ta thực hiện điều này một cách hiệu quả và ngắn gọn.

Trong bài thực hành này, chúng ta sẽ khám phá và sử dụng một số thuật toán tìm kiếm nâng cao phổ biến nhất có sẵn trong STL, tập trung vào thư viện <algorithm>.

1. Nhắc Lại `find` - Tìm Kiếm Tuyến Tính Cơ Bản

Trước khi đi xa hơn, hãy nhắc lại về hàm find. Đây là thuật toán tìm kiếm tuyến tính (linear search) cơ bản nhất. Nó duyệt qua từng phần tử trong một phạm vi (range) từ đầu đến cuối cho đến khi tìm thấy phần tử khớp hoặc duyệt hết phạm vi.

Đặc điểm:

Không yêu cầu phạm vi phải được sắp xếp.
Hiệu quả với các tập dữ liệu nhỏ hoặc khi phần tử cần tìm có khả năng nằm ở đầu.
Độ phức tạp thời gian: O(n) trong trường hợp xấu nhất (n là số phần tử).

Ví dụ:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iterator>

int main() {
    using namespace std;

    vector<int> so = {10, 5, 20, 15, 25};
    int gtTim = 15;

    auto it = find(so.begin(), so.end(), gtTim);

    if (it != so.end()) {
        cout << "Tim thay " << gtTim << " tai vi tri index: " << distance(so.begin(), it) << endl;
    } else {
        cout << gtTim << " khong co trong vector." << endl;
    }

    vector<string> chuoi = {"apple", "banana", "cherry"};
    string cTim = "banana";

    auto itC = find(chuoi.begin(), chuoi.end(), cTim);

    if (itC != chuoi.end()) {
        cout << "Tim thay '" << cTim << "' trong vector string." << endl;
    } else {
        cout << "'" << cTim << "' khong co trong vector string." << endl;
    }

    return 0;
}

Output:

Tim thay 15 tai vi tri index: 3
Tim thay 'banana' trong vector string.

Giải thích:

find nhận vào hai iterator chỉ định phạm vi tìm kiếm (numbers.begin(), numbers.end()) và giá trị cần tìm (value_to_find).
Nó trả về một iterator trỏ đến phần tử đầu tiên tìm thấy khớp với giá trị, hoặc numbers.end() nếu không tìm thấy.
Chúng ta so sánh iterator trả về với numbers.end() để xác định xem phần tử có tồn tại hay không.
distance(numbers.begin(), it) giúp tính toán chỉ mục (index) của phần tử tìm thấy.

find rất đơn giản và linh hoạt (vì không yêu cầu sắp xếp), nhưng với tập dữ liệu lớn và việc tìm kiếm diễn ra thường xuyên, hiệu suất của nó có thể trở thành vấn đề.

2. `binary_search` - Sức Mạnh Của Dữ Liệu Đã Sắp Xếp

Khi dữ liệu của bạn đã được sắp xếp (sorted), bạn có thể tận dụng thuật toán tìm kiếm nhị phân (binary search), một trong những thuật toán tìm kiếm hiệu quả nhất. binary_search trong C++ STL cho phép chúng ta làm điều này.

Đặc điểm:

Bắt buộc: Phạm vi tìm kiếm phải được sắp xếp theo thứ tự không giảm (non-decreasing).
Chỉ kiểm tra sự tồn tại của phần tử (trả về bool). Nó không trả về vị trí của phần tử.
Độ phức tạp thời gian: O(log n) - cực kỳ nhanh với dữ liệu lớn so với O(n).

Ví dụ:

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;

    vector<int> soSX = {5, 10, 15, 20, 25};
    int gtCo = 15;
    int gtKhong = 12;

    bool coCo = binary_search(soSX.begin(), soSX.end(), gtCo);
    bool coKhong = binary_search(soSX.begin(), soSX.end(), gtKhong);

    if (coCo) {
        cout << "Tim thay " << gtCo << " trong vector (su dung binary_search)." << endl;
    } else {
        cout << gtCo << " khong co trong vector (su dung binary_search)." << endl;
    }

    if (coKhong) {
        cout << "Tim thay " << gtKhong << " trong vector (su dung binary_search)." << endl;
    } else {
        cout << gtKhong << " khong co trong vector (su dung binary_search)." << endl;
    }

    vector<int> soCX = {30, 10, 50, 20, 40};
    sort(soCX.begin(), soCX.end());
    int gtSauSX = 40;

    bool coSauSX = binary_search(soCX.begin(), soCX.end(), gtSauSX);

    if (coSauSX) {
         cout << "Tim thay " << gtSauSX << " trong vector sau khi sap xep (su dung binary_search)." << endl;
    }

    return 0;
}

Output:

Tim thay 15 trong vector (su dung binary_search).
12 khong co trong vector (su dung binary_search).
Tim thay 40 trong vector sau khi sap xep (su dung binary_search).

Giải thích:

binary_search cũng nhận vào phạm vi và giá trị cần tìm.
Điểm khác biệt quan trọng là nó yêu cầu phạm vi phải được sắp xếp. Nếu không, kết quả sẽ không chính xác.
Nó chỉ trả về true nếu phần tử tồn tại trong phạm vi, và false nếu không. Nó không cho biết vị trí.
Trước khi sử dụng binary_search trên dữ liệu chưa sắp xếp, bạn phải sắp xếp nó trước bằng sort. Chi phí sắp xếp ban đầu (thường là O(n log n)) có thể được bù đắp nhanh chóng nếu bạn thực hiện nhiều thao tác tìm kiếm sau đó (mỗi lần tìm kiếm chỉ mất O(log n)).

3. `lower_bound` và `upper_bound` - Tìm Kiếm Vị Trí Cận Dưới và Cận Trên

Đôi khi, bạn không chỉ muốn biết liệu một giá trị có tồn tại hay không, mà còn muốn biết vị trí mà nó (hoặc một giá trị lớn hơn nó) nên nằm ở đâu. lower_bound và upper_bound là các công cụ hoàn hảo cho việc này, đặc biệt hữu ích khi làm việc với dữ liệu đã sắp xếp hoặc khi cần tìm kiếm một phạm vi các phần tử có cùng giá trị.

Cả hai hàm này đều yêu cầu phạm vi đầu vào phải được sắp xếp.

lower_bound(first, last, val): Trả về một iterator trỏ đến phần tử đầu tiên trong phạm vi [first, last) không nhỏ hơn val. Nếu tất cả phần tử đều nhỏ hơn val, nó trả về last.
upper_bound(first, last, val): Trả về một iterator trỏ đến phần tử đầu tiên trong phạm vi [first, last) lớn hơn val. Nếu tất cả phần tử đều nhỏ hơn hoặc bằng val, nó trả về last.

Ứng dụng phổ biến:

Tìm vị trí để chèn một phần tử mới mà vẫn giữ được tính sắp xếp.
Đếm số lần xuất hiện của một giá trị cụ thể.

Ví dụ:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    using namespace std;

    vector<int> so = {10, 20, 20, 30, 40, 50};

    int gT1 = 20;
    auto itDuoi = lower_bound(so.begin(), so.end(), gT1);

    cout << "lower_bound cho gia tri " << gT1 << " tro den vi tri index: "
              << distance(so.begin(), itDuoi) << endl;

    int gT2 = 25;
    auto itDuoiKhongCo = lower_bound(so.begin(), so.end(), gT2);
     cout << "lower_bound cho gia tri " << gT2 << " tro den vi tri index: "
              << distance(so.begin(), itDuoiKhongCo) << endl;

    int gT3 = 20;
    auto itTren = upper_bound(so.begin(), so.end(), gT3);

    cout << "upper_bound cho gia tri " << gT3 << " tro den vi tri index: "
              << distance(so.begin(), itTren) << endl;

    int gT4 = 55;
     auto itTrenKhongCo = upper_bound(so.begin(), so.end(), gT4);
      cout << "upper_bound cho gia tri " << gT4 << " tro den vi tri index: "
              << distance(so.begin(), itTrenKhongCo) << endl;

    auto dem = distance(itDuoi, itTren);
    cout << "So lan xuat hien cua gia tri 20: " << dem << endl;

    return 0;
}

Output:

lower_bound cho gia tri 20 tro den vi tri index: 1
lower_bound cho gia tri 25 tro den vi tri index: 3
upper_bound cho gia tri 20 tro den vi tri index: 3
upper_bound cho gia tri 55 tro den vi tri index: 6
So lan xuat hien cua gia tri 20: 2

Giải thích:

lower_bound và upper_bound đều hoạt động trên phạm vi đã sắp xếp.
lower_bound tìm điểm bắt đầu của nhóm các phần tử có giá trị val.
upper_bound tìm điểm kết thúc của nhóm các phần tử có giá trị val (iterator trỏ đến phần tử ngay sau phần tử cuối cùng có giá trị val).
Khoảng iterator [lower_it, upper_it) chính là phạm vi chứa tất cả các phần tử có giá trị bằng val.
Chúng ta có thể tính số phần tử trong khoảng này bằng distance(lower_it, upper_it).

4. `equal_range` - Tìm Kiếm Toàn Bộ Phạm Vi Bằng Nhau

Hàm equal_range là sự kết hợp tiện lợi của lower_bound và upper_bound. Nó thực hiện cả hai phép tìm kiếm và trả về một pair chứa hai iterator: iterator trả về từ lower_bound và iterator trả về từ upper_bound.

Đặc điểm:

Bắt buộc: Phạm vi tìm kiếm phải được sắp xếp.
Trả về một pair<Iterator, Iterator> chỉ định phạm vi [lower_bound_iterator, upper_bound_iterator) chứa tất cả các phần tử bằng với giá trị cần tìm.
Độ phức tạp thời gian: O(log n).

Ví dụ:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>

int main() {
    using namespace std;

    vector<int> so = {10, 20, 20, 30, 40, 50};
    int gT = 20;

    auto phamVi = equal_range(so.begin(), so.end(), gT);

    cout << "Phan tu dau tien >= " << gT << " tai index: "
              << distance(so.begin(), phamVi.first) << endl;

    cout << "Phan tu dau tien > " << gT << " tai index: "
              << distance(so.begin(), phamVi.second) << endl;

    auto dem = distance(phamVi.first, phamVi.second);
    cout << "So lan xuat hien cua gia tri " << gT << ": " << dem << endl;

    if (phamVi.first != phamVi.second) {
        cout << gT << " ton tai trong vector." << endl;
    } else {
        cout << gT << " khong ton tai trong vector (hoac khong co phan tu nao bang)." << endl;
    }

    return 0;
}

Output:

Phan tu dau tien >= 20 tai index: 1
Phan tu dau tien > 20 tai index: 3
So lan xuat hien cua gia tri 20: 2
20 ton tai trong vector.

Giải thích:

equal_range trả về một cặp iterator định nghĩa phạm vi của các phần tử bằng giá trị tìm kiếm.
range.first tương đương với kết quả của lower_bound.
range.second tương đương với kết quả của upper_bound.
Sự khác biệt giữa hai iterator này (distance(range.first, range.second)) cho ta biết có bao nhiêu phần tử bằng với giá trị cần tìm.
Nếu range.first == range.second, điều đó có nghĩa là không có phần tử nào bằng với giá trị tìm kiếm trong phạm vi.

5. `find_if` - Tìm Kiếm Với Điều Kiện Tùy Chỉnh

Đôi khi, bạn cần tìm kiếm một phần tử không phải dựa trên giá trị cụ thể, mà dựa trên một điều kiện nhất định. Ví dụ, tìm số chẵn đầu tiên, tìm chuỗi rỗng đầu tiên, hoặc tìm đối tượng đầu tiên thỏa mãn một thuộc tính nào đó. find_if được thiết kế để giải quyết vấn đề này một cách linh hoạt.

Đặc điểm:

Không yêu cầu phạm vi phải được sắp xếp.
Tìm kiếm phần tử đầu tiên mà một predicate (hàm hoặc lambda trả về bool) trả về true cho phần tử đó.
Độ phức tạp thời gian: O(n) trong trường hợp xấu nhất.

Ví dụ:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iterator>

bool laSoChan(int n) {
    return n % 2 == 0;
}

int main() {
    using namespace std;

    vector<int> so = {1, 3, 5, 8, 9, 10, 12};

    auto itChan = find_if(so.begin(), so.end(), laSoChan);

    if (itChan != so.end()) {
        cout << "So chan dau tien la: " << *itChan
                  << " tai vi tri index: " << distance(so.begin(), itChan) << endl;
    } else {
        cout << "Khong tim thay so chan nao." << endl;
    }

    vector<string> chuoi = {"cat", "dog", "elephant", "fox"};

    auto itDai = find_if(chuoi.begin(), chuoi.end(),
                                     [](const string& s){
                                         return s.length() > 5;
                                     });

    if (itDai != chuoi.end()) {
        cout << "Chuoi dau tien co do dai > 5 la: '" << *itDai << "'"
                  << " tai vi tri index: " << distance(chuoi.begin(), itDai) << endl;
    } else {
        cout << "Khong tim thay chuoi nao co do dai > 5." << endl;
    }

    return 0;
}

Output:

So chan dau tien la: 8 tai vi tri index: 3
Chuoi dau tien co do dai > 5 la: 'elephant' tai vi tri index: 2

Giải thích:

find_if nhận phạm vi và một predicate. Predicate này là một đối tượng có thể được gọi (hàm, function object, lambda expression) nhận một tham số (là một phần tử trong phạm vi) và trả về bool.
Nếu predicate trả về true cho một phần tử, find_if sẽ dừng lại và trả về iterator trỏ đến phần tử đó.
Nếu predicate trả về false cho tất cả các phần tử trong phạm vi, nó trả về iterator end().
Ví dụ trên minh họa việc sử dụng cả hàm thường (isEven) và lambda expression (để kiểm tra độ dài chuỗi) làm predicate. Lambda expression thường được ưa chuộng vì tính gọn nhẹ khi predicate đơn giản và chỉ dùng một lần.

Comments

There are no comments at the moment.