Bài 23.2: Bài tập thực hành lower_bound trong C++

Chào mừng các bạn trở lại với series bài viết về C++! Hôm nay, chúng ta sẽ cùng khám phá một công cụ rất hữu ích trong Thư viện Chuẩn C++ (STL), đó là hàm lower_bound. Đây là một phần quan trọng của <algorithm>, giúp chúng ta thực hiện tìm kiếm hiệu quả trên các dãy dữ liệu đã được sắp xếp.

`lower_bound` là gì?

Trong thế giới lập trình, việc tìm kiếm một phần tử trong một tập hợp dữ liệu là một tác vụ cực kỳ phổ biến. Khi dữ liệu chưa được sắp xếp, chúng ta thường phải duyệt qua từng phần tử (tìm kiếm tuyến tính), mất O(n) thời gian (với n là số phần tử). Nhưng nếu dữ liệu của chúng ta đã được sắp xếp, chúng ta có thể sử dụng các thuật toán tìm kiếm nhanh hơn nhiều, điển hình là tìm kiếm nhị phân.

lower_bound chính là hiện thực của thuật toán tìm kiếm nhị phân trong STL C++. Cụ thể, nó tìm kiếm trong một phạm vi (được định nghĩa bởi hai iterator) và trả về một iterator trỏ đến phần tử đầu tiên trong phạm vi đó không nhỏ hơn một giá trị cho trước.

Nghe có vẻ hơi phức tạp một chút với cụm từ "không nhỏ hơn"? Hãy hiểu đơn giản: nó sẽ trả về iterator tới phần tử đầu tiên mà bằng hoặc lớn hơn giá trị bạn đang tìm.

Điều kiện tiên quyết quan trọng nhất: Phạm vi dữ liệu mà bạn tìm kiếm phải được sắp xếp theo thứ tự tăng dần (mặc định) hoặc theo một tiêu chí nào đó mà bạn chỉ rõ. Nếu không, kết quả của lower_bound sẽ không chính xác và không xác định (undefined behavior).

Cú pháp cơ bản của `lower_bound`

Hàm lower_bound thường có hai dạng chính:

Dạng mặc định (sử dụng toán tử <):
```
iterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val);
```
- first, last: Các iterator định nghĩa phạm vi tìm kiếm [first, last). Lưu ý phạm vi là nửa đóng, tức bao gồm first nhưng không bao gồm last.
- val: Giá trị mà bạn muốn tìm vị trí "không nhỏ hơn" đầu tiên của nó.
- iterator: Trả về một iterator. Iterator này trỏ tới phần tử đầu tiên trong [first, last) sao cho phần tử đó không nhỏ hơn val. Nếu tất cả các phần tử trong phạm vi đều nhỏ hơn val, nó sẽ trả về last.
Dạng sử dụng Comparator tùy chỉnh:
```
iterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val, Compare comp);
```
- Tương tự như dạng trên, nhưng có thêm tham số comp.
- comp: Một đối tượng hàm (functor) hoặc lambda expression định nghĩa phép so sánh "nhỏ hơn". comp(a, b) trả về true nếu a được coi là nhỏ hơn b. Phạm vi [first, last) phải được sắp xếp dựa trên tiêu chí so sánh này. lower_bound sẽ tìm phần tử đầu tiên e trong phạm vi sao cho comp(e, val) là false.

Tại sao lại là "không nhỏ hơn"?

Khái niệm "không nhỏ hơn" (!comp(element, val) hoặc !(element < val)) là trung tâm của lower_bound. Trong một dãy đã sắp xếp tăng dần:

Nếu val có mặt trong dãy, lower_bound sẽ trỏ tới vị trí đầu tiên của val. Ví dụ: trong {1, 2, 2, 3, 4}, lower_bound cho val=2 sẽ trỏ tới số 2 đầu tiên.
Nếu val không có mặt trong dãy, lower_bound sẽ trỏ tới vị trí mà val sẽ được chèn vào để dãy vẫn giữ nguyên tính chất sắp xếp. Vị trí này chính là phần tử đầu tiên lớn hơn val. Ví dụ: trong {1, 3, 5}, lower_bound cho val=2 sẽ trỏ tới số 3 (vị trí mà 2 có thể được chèn vào). lower_bound cho val=4 sẽ trỏ tới số 5. lower_bound cho val=6 sẽ trỏ tới end() iterator.

Ví dụ Minh Họa Cơ Bản

Chúng ta hãy bắt đầu với một ví dụ đơn giản sử dụng vector<int> đã được sắp xếp.

#include <iostream>
#include <vector>
#include <algorithm> // Cần cho lower_bound
#include <iterator>  // Cần cho distance

int main() {
    vector<int> data = {10, 20, 30, 30, 40, 50};

    // Case 1: Tìm một giá trị có mặt trong vector (xuất hiện lần đầu)
    int value1 = 30;
    auto it1 = lower_bound(data.begin(), data.end(), value1);

    // it1 là một iterator. Để kiểm tra xem nó có trỏ đến phần tử hợp lệ không,
    // ta so sánh với data.end(). Nếu it1 == data.end(), nghĩa là
    // không có phần tử nào >= value1 (tức là tất cả đều nhỏ hơn value1).
    if (it1 != data.end()) {
        cout << "Phan tu khong nho hon " << value1 << " dau tien tim thay la: " << *it1 << endl;
        // Để lấy chỉ số (index) của phần tử đó:
        int index1 = distance(data.begin(), it1);
        cout << "Tai chi so (index): " << index1 << endl;
    } else {
        cout << "Khong tim thay phan tu khong nho hon " << value1 << " trong vector." << endl;
    }

    cout << "---" << endl;

    // Case 2: Tìm một giá trị không có mặt (nhưng nằm trong phạm vi)
    int value2 = 35;
    auto it2 = lower_bound(data.begin(), data.end(), value2);

    if (it2 != data.end()) {
        cout << "Phan tu khong nho hon " << value2 << " dau tien tim thay la: " << *it2 << endl;
        int index2 = distance(data.begin(), it2);
        cout << "Tai chi so (index): " << index2 << endl;
        // Lưu ý: *it2 (40) là phần tử đầu tiên >= 35. Vị trí này (index 4)
        // chính là nơi mà 35 sẽ được chèn vào để giữ vector sorted.
    } else {
         cout << "Khong tim thay phan tu khong nho hon " << value2 << " trong vector." << endl;
    }

    cout << "---" << endl;

    // Case 3: Tìm một giá trị lớn hơn tất cả các phần tử trong vector
    int value3 = 60;
    auto it3 = lower_bound(data.begin(), data.end(), value3);

    if (it3 != data.end()) {
        // Dòng này sẽ không được in vì it3 == data.end()
        cout << "Phan tu khong nho hon " << value3 << " dau tien tim thay la: " << *it3 << endl;
        int index3 = distance(data.begin(), it3);
        cout << "Tai chi so (index): " << index3 << endl;
    } else {
         // it3 == data.end() nghĩa là mọi phần tử đều nhỏ hơn value3.
         // iterator data.end() đánh dấu vị trí *sau* phần tử cuối cùng.
         // Chỉ số của data.end() chính là kích thước của vector.
         int index3 = distance(data.begin(), it3);
         cout << "Khong tim thay phan tu khong nho hon " << value3 << " trong vector." << endl;
         cout << "Vi tri ma " << value3 << " se duoc chen vao la: " << index3 << " (chinh la data.end())" << endl;
    }

    return 0;
}

Giải thích code:

Chúng ta khai báo một vector<int> tên là data và khởi tạo nó với các giá trị đã được sắp xếp tăng dần.
Hàm lower_bound được gọi với data.begin(), data.end() (phạm vi tìm kiếm) và giá trị cần tìm.
Kết quả trả về là một iterator. Chúng ta lưu nó vào biến it.
Để kiểm tra xem lower_bound có tìm thấy vị trí hợp lệ (không phải end()) hay không, chúng ta so sánh it với data.end().
Nếu it != data.end(), nghĩa là đã tìm thấy phần tử đầu tiên không nhỏ hơn giá trị cần tìm. Ta có thể truy cập giá trị đó bằng *it.
Để lấy chỉ số (index) của phần tử đó, chúng ta sử dụng distance(data.begin(), it). Hàm này tính số bước từ data.begin() đến it.
Ví dụ 1: Tìm 30. lower_bound tìm thấy số 30 đầu tiên tại index 2.
Ví dụ 2: Tìm 35. 35 không có trong vector. lower_bound tìm thấy phần tử đầu tiên không nhỏ hơn 35, đó là 40 tại index 4. Đây chính là vị trí mà 35 sẽ được chèn vào.
Ví dụ 3: Tìm 60. Mọi phần tử đều nhỏ hơn 60. lower_bound trả về data.end(). Chỉ số tương ứng là kích thước của vector (6), vị trí sau phần tử cuối cùng.

Sử dụng `lower_bound` với Comparator Tùy Chỉnh

Giả sử chúng ta có một vector được sắp xếp theo thứ tự giảm dần và chúng ta muốn sử dụng lower_bound trên nó. Chúng ta cần cung cấp một comparator. Comparator này cần định nghĩa khi nào một phần tử nhỏ hơn giá trị cần tìm theo tiêu chí sắp xếp giảm dần của chúng ta.

Ví dụ: Tìm phần tử đầu tiên không nhỏ hơn 30 trong vector {50, 40, 30, 30, 20, 10}. Trong thứ tự giảm dần, "không nhỏ hơn 30" có nghĩa là "lớn hơn hoặc bằng 30". Comparator greater<int>() định nghĩa a > b. lower_bound(..., value, greater<int>()) sẽ tìm phần tử e đầu tiên sao cho greater<int>(e, value) là false, tức e <= value.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <functional> // Cần cho greater

int main() {
    // Vector sap xep giam dan
    vector<int> data_desc = {50, 40, 30, 30, 20, 10};

    // Tim phan tu dau tien KHONG NHO HON 30 theo thu tu giam dan
    // Trong thu tu giam dan, "khong nho hon" nghia la "lon hon hoac bang".
    // Ta dung comparator greater<int>()
    int value = 30;
    auto it = lower_bound(data_desc.begin(), data_desc.end(), value, greater<int>());

    if (it != data_desc.end()) {
        cout << "Trong vector giam dan, phan tu KHONG NHO HON " << value << " (tuc >= " << value << ") dau tien la: " << *it << endl;
        int index = distance(data_desc.begin(), it);
        cout << "Tai chi so (index): " << index << endl; // Ket qua se la index 2 (so 30 dau tien)
    } else {
        cout << "Khong tim thay phan tu nao >= " << value << " trong vector giam dan." << endl;
    }

     cout << "---" << endl;

    // Tim phan tu dau tien KHONG NHO HON 35 theo thu tu giam dan
    // Trong thu tu giam dan, "khong nho hon 35" nghia la "lon hon hoac bang 35".
    // Phan tu dau tien >= 35 la 40.
    value = 35;
    it = lower_bound(data_desc.begin(), data_desc.end(), value, greater<int>());

    if (it != data_desc.end()) {
        cout << "Trong vector giam dan, phan tu KHONG NHO HON " << value << " (tuc >= " << value << ") dau tien la: " << *it << endl;
        int index = distance(data_desc.begin(), it);
        cout << "Tai chi so (index): " << index << endl; // Ket qua se la index 1 (so 40)
    } else {
        cout << "Khong tim thay phan tu nao >= " << value << " trong vector giam dan." << endl;
    }

    return 0;
}

Giải thích code:

Vector data_desc được sắp xếp giảm dần.
Chúng ta sử dụng greater<int>() làm comparator. greater<int>()(a, b) trả về true nếu a > b.
lower_bound với comparator comp tìm phần tử e đầu tiên sao cho comp(e, value) là false. Với greater, điều này có nghĩa là tìm e đầu tiên sao cho greater(e, value) là false, tức !(e > value), hay e <= value.
Kết quả: Khi tìm value = 30, nó tìm phần tử đầu tiên e sao cho e <= 30. Phần tử đó là số 30 đầu tiên tại index 2.
Khi tìm value = 35, nó tìm phần tử đầu tiên e sao cho e <= 35. Phần tử đó là số 40 tại index 1. Vị trí này là nơi 35 sẽ được chèn vào để giữ vector được "gần sắp xếp" theo thứ tự giảm dần (hoặc chính xác hơn, đây là ranh giới giữa các phần tử > 35 và <= 35).

Việc sử dụng comparator cho phép lower_bound hoạt động trên các kiểu sắp xếp khác nhau, hoặc trên các đối tượng phức tạp hơn dựa trên một thuộc tính cụ thể.

`lower_bound` với Mảng (Array)

lower_bound cũng hoạt động trên mảng C-style vì con trỏ có thể hoạt động như iterator.

#include <iostream>
#include <algorithm>
#include <iterator> // Cần cho distance hoặc begin/end cho mảng

int main() {
    int data_array[] = {5, 15, 25, 35, 45, 55};
    // Kich thuoc mang
    int n = sizeof(data_array) / sizeof(data_array[0]);

    // Tim vi tri cho gia tri 35
    int value1 = 35;
    // Co the dung con tro hoac begin/end (tu <iterator>)
    auto it1 = lower_bound(data_array, data_array + n, value1);
    // Hoac: auto it1 = lower_bound(begin(data_array), end(data_array), value1);


    if (it1 != (data_array + n)) { // So sanh voi con tro sau phan tu cuoi
        cout << "Trong mang, phan tu khong nho hon " << value1 << " dau tien la: " << *it1 << endl;
        int index1 = distance(data_array, it1); // Tinh khoang cach tu con tro dau mang
        cout << "Tai chi so (index): " << index1 << endl;
    } else {
        cout << "Khong tim thay phan tu nao >= " << value1 << " trong mang." << endl;
    }

    cout << "---" << endl;

    // Tim vi tri cho gia tri 22 (khong co trong mang)
    int value2 = 22;
    auto it2 = lower_bound(data_array, data_array + n, value2);

    if (it2 != (data_array + n)) {
        cout << "Trong mang, phan tu khong nho hon " << value2 << " dau tien la: " << *it2 << endl;
        int index2 = distance(data_array, it2);
        cout << "Tai chi so (index): " << index2 << endl; // Ket qua se la index 2 (so 25)
    } else {
         cout << "Khong tim thay phan tu nao >= " << value2 << " trong mang." << endl;
    }


    return 0;
}

Giải thích code:

Mảng data_array cũng phải được sắp xếp.
Phạm vi tìm kiếm được định nghĩa bởi con trỏ đầu mảng data_array và con trỏ sau phần tử cuối cùng data_array + n.
Cách sử dụng và ý nghĩa của iterator trả về hoàn toàn tương tự như với vector. distance được sử dụng để tính index từ con trỏ đầu mảng.

Tìm kiếm với Đối Tượng Tùy Chỉnh

Giả sử chúng ta có một cấu trúc dữ liệu tùy chỉnh, ví dụ struct Item có ID và tên, và chúng ta muốn tìm kiếm dựa trên ID.

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

struct Item {
    int id;
    string name;

    // Can thiet neu muon sap xep hoac dung default lower_bound tren vector<Item>
    // bool operator<(const Item& other) const {
    //     return id < other.id;
    // }
    // Tuy nhien, khi tim kiem voi mot gia tri int (id), ta can comparator chuyen biet hon.
};

// Comparator cho lower_bound khi tim kiem Item theo ID voi mot gia tri int
// Ham nay kiem tra xem mot Item co "nho hon" mot gia tri int khong
bool compareItemWithInt(const Item& item, int value) {
    return item.id < value;
}

int main() {
    // Vector cac Item, sap xep theo ID tang dan
    vector<Item> items = {
        {10, "Laptop"},
        {20, "Mouse"},
        {30, "Keyboard"},
        {30, "Monitor"}, // Co 2 items co ID 30
        {40, "Webcam"}
    };

    // Tim Item dau tien co ID >= 30
    int search_id = 30;
    auto it = lower_bound(items.begin(), items.end(), search_id, compareItemWithInt);

    if (it != items.end()) {
        cout << "Item dau tien co ID KHONG NHO HON " << search_id << " (tuc >= " << search_id << ") la:" << endl;
        cout << "  ID: " << it->id << ", Name: " << it->name << endl;
        int index = distance(items.begin(), it);
        cout << "Tai chi so (index): " << index << endl; // Ket qua se la index 2 (Keyboard)
    } else {
        cout << "Khong tim thay item nao co ID >= " << search_id << "." << endl;
    }

     cout << "---" << endl;

    // Tim Item dau tien co ID >= 25 (khong co trong vector)
    search_id = 25;
    it = lower_bound(items.begin(), items.end(), search_id, compareItemWithInt);

    if (it != items.end()) {
        cout << "Item dau tien co ID KHONG NHO HON " << search_id << " (tuc >= " << search_id << ") la:" << endl;
        cout << "  ID: " << it->id << ", Name: " << it->name << endl;
        int index = distance(items.begin(), it);
        cout << "Tai chi so (index): " << index << endl; // Ket qua se la index 2 (Keyboard - ID 30)
    } else {
        cout << "Khong tim thay item nao co ID >= " << search_id << "." << endl;
    }


    return 0;
}

Giải thích code:

Chúng ta có vector items chứa các đối tượng Item, được sắp xếp theo thuộc tính id.
Để tìm kiếm một int (search_id) trong vector Item, chúng ta cần một comparator có thể so sánh một Item với một int.
Hàm compareItemWithInt(const Item& item, int value) làm điều này. Nó trả về true nếu item.id < value.
lower_bound sử dụng comparator này để tìm phần tử Item đầu tiên e trong vector sao cho compareItemWithInt(e, search_id) là false. Điều này có nghĩa là e.id < search_id là false, hay e.id >= search_id.
Ví dụ 1: Tìm search_id = 30. lower_bound tìm thấy Item đầu tiên có ID >= 30, đó là Item "Keyboard" tại index 2.
Ví dụ 2: Tìm search_id = 25. lower_bound tìm thấy Item đầu tiên có ID >= 25, đó là Item "Keyboard" tại index 2. Đây là vị trí mà một Item có ID 25 sẽ được chèn vào.

Lưu ý rằng comparator cho lower_bound(first, last, value, comp) có dạng comp(element_in_range, value). Nó định nghĩa khi nào một phần tử trong dãy được coi là nhỏ hơn giá trị đang tìm.

Hiệu Suất

Điểm mạnh lớn nhất của lower_bound là hiệu quả của nó. Vì nó dựa trên thuật toán tìm kiếm nhị phân:

Đối với các iterator truy cập ngẫu nhiên (random access iterators) như vector, deque, array, hoặc con trỏ C-style, độ phức tạp thời gian là O(log n), với n là số phần tử trong phạm vi. Đây là cực kỳ nhanh chóng đối với các tập dữ liệu lớn.
Đối với các iterator song hướng (bidirectional iterators) như list, độ phức tạp là O(n) vì không thể truy cập ngẫu nhiên; thuật toán vẫn phải duyệt tuần tự. Tuy nhiên, list thường không được sắp xếp thường xuyên để sử dụng lower_bound một cách hiệu quả; các container như map hoặc set (thường được hiện thực bằng cây cân bằng) là lựa chọn tốt hơn cho dữ liệu cần được sắp xếp và tìm kiếm/chèn nhanh chóng.

Khi nào sử dụng `lower_bound`?

Bạn nên sử dụng lower_bound khi:

Bạn cần tìm kiếm trên một dãy dữ liệu đã được sắp xếp.
Bạn cần tìm vị trí của phần tử đầu tiên không nhỏ hơn một giá trị cụ thể.
Bạn muốn tận dụng hiệu quả O(log n) của tìm kiếm nhị phân (trên các container phù hợp).

Nó thường được dùng để:

Tìm kiếm một phần tử trong tập dữ liệu lớn đã sắp xếp.
Tìm vị trí chèn một phần tử mới vào dãy đã sắp xếp để duy trì tính sắp xếp.
Kết hợp với upper_bound để tìm tất cả các phần tử bằng một giá trị cụ thể trong một dãy đã sắp xếp (phạm vi [lower_bound(value), upper_bound(value))).

Comments

There are no comments at the moment.