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:

  1. 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.

  2. 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>
#include <iterator>

using namespace std;

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

    // Case 1
    int g1 = 30;
    auto it1 = lower_bound(v.begin(), v.end(), g1);
    if (it1 != v.end()) {
        cout << "PT >= " << g1 << " dau tien: " << *it1 << endl;
        int idx1 = distance(v.begin(), it1);
        cout << "Tai chi so: " << idx1 << endl;
    } else {
        cout << "Khong tim thay PT >= " << g1 << endl;
    }
    cout << "---\n";

    // Case 2
    int g2 = 35;
    auto it2 = lower_bound(v.begin(), v.end(), g2);
    if (it2 != v.end()) {
        cout << "PT >= " << g2 << " dau tien: " << *it2 << endl;
        int idx2 = distance(v.begin(), it2);
        cout << "Tai chi so: " << idx2 << endl;
    } else {
         cout << "Khong tim thay PT >= " << g2 << endl;
    }
    cout << "---\n";

    // Case 3
    int g3 = 60;
    auto it3 = lower_bound(v.begin(), v.end(), g3);
    if (it3 != v.end()) {
        cout << "PT >= " << g3 << " dau tien: " << *it3 << endl;
        int idx3 = distance(v.begin(), it3);
        cout << "Tai chi so: " << idx3 << endl;
    } else {
         int idx3 = distance(v.begin(), it3);
         cout << "Khong tim thay PT >= " << g3 << endl;
         cout << "Vi tri chen: " << idx3 << " (end())" << endl;
    }
    return 0;
}

Output:

PT >= 30 dau tien: 30
Tai chi so: 2
---
PT >= 35 dau tien: 40
Tai chi so: 4
---
Khong tim thay PT >= 60
Vi tri chen: 6 (end())

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>

using namespace std;

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

    // Case 1
    int g = 30;
    auto it = lower_bound(vd.begin(), vd.end(), g, greater<int>());

    if (it != vd.end()) {
        cout << "Vec giam dan, PT >= " << g << " dau tien: " << *it << endl;
        int idx = distance(vd.begin(), it);
        cout << "Tai chi so: " << idx << endl;
    } else {
        cout << "Khong tim thay PT nao >= " << g << " trong vec giam dan." << endl;
    }
    cout << "---\n";

    // Case 2
    g = 35;
    it = lower_bound(vd.begin(), vd.end(), g, greater<int>());

    if (it != vd.end()) {
        cout << "Vec giam dan, PT >= " << g << " dau tien: " << *it << endl;
        int idx = distance(vd.begin(), it);
        cout << "Tai chi so: " << idx << endl;
    } else {
        cout << "Khong tim thay PT nao >= " << g << " trong vec giam dan." << endl;
    }
    return 0;
}

Output:

Vec giam dan, PT >= 30 dau tien: 30
Tai chi so: 2
---
Vec giam dan, PT >= 35 dau tien: 40
Tai chi so: 1

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>

using namespace std;

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

    // Case 1
    int g1 = 35;
    auto it1 = lower_bound(begin(a), end(a), g1);

    if (it1 != end(a)) {
        cout << "Mang, PT >= " << g1 << " dau tien: " << *it1 << endl;
        int idx1 = distance(begin(a), it1);
        cout << "Tai chi so: " << idx1 << endl;
    } else {
        cout << "Khong tim thay PT nao >= " << g1 << " trong mang." << endl;
    }
    cout << "---\n";

    // Case 2
    int g2 = 22;
    auto it2 = lower_bound(begin(a), end(a), g2);

    if (it2 != end(a)) {
        cout << "Mang, PT >= " << g2 << " dau tien: " << *it2 << endl;
        int idx2 = distance(begin(a), it2);
        cout << "Tai chi so: " << idx2 << endl;
    } else {
         cout << "Khong tim thay PT nao >= " << g2 << " trong mang." << endl;
    }
    return 0;
}

Output:

Mang, PT >= 35 dau tien: 35
Tai chi so: 3
---
Mang, PT >= 22 dau tien: 25
Tai chi so: 2

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>

using namespace std;

struct I {
    int id;
    string ten;
};

int main() {
    vector<I> ds = {
        {10, "Laptop"},
        {20, "Mouse"},
        {30, "Keyboard"},
        {30, "Monitor"},
        {40, "Webcam"}
    };

    // Case 1
    int id_tim = 30;
    auto it = lower_bound(ds.begin(), ds.end(), id_tim,
                          [](const I& item, int val) { return item.id < val; });

    if (it != ds.end()) {
        cout << "Item ID >= " << id_tim << " dau tien:\n";
        cout << "  ID: " << it->id << ", Ten: " << it->ten << endl;
        int idx = distance(ds.begin(), it);
        cout << "Tai chi so: " << idx << endl;
    } else {
        cout << "Khong tim thay item nao ID >= " << id_tim << ".\n";
    }
    cout << "---\n";

    // Case 2
    id_tim = 25;
    it = lower_bound(ds.begin(), ds.end(), id_tim,
                     [](const I& item, int val) { return item.id < val; });

    if (it != ds.end()) {
        cout << "Item ID >= " << id_tim << " dau tien:\n";
        cout << "  ID: " << it->id << ", Ten: " << it->ten << endl;
        int idx = distance(ds.begin(), it);
        cout << "Tai chi so: " << idx << endl;
    } else {
        cout << "Khong tim thay item nao ID >= " << id_tim << ".\n";
    }
    return 0;
}

Output:

Item ID >= 30 dau tien:
  ID: 30, Ten: Keyboard
Tai chi so: 2
---
Item ID >= 25 dau tien:
  ID: 30, Ten: Keyboard
Tai chi so: 2

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:

  1. Bạn cần tìm kiếm trên một dãy dữ liệu đã được sắp xếp.
  2. 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ể.
  3. 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.