Bài 23.3: Bài tập thực hành upper_bound trong C++

Chào mừng trở lại với series blog về C++! Hôm nay, chúng ta sẽ cùng khám phá một công cụ cực kỳ hữu ích trong C++ Standard Library (STL), đó là hàm upper_bound. Nếu bạn thường xuyên làm việc với các tập dữ liệu đã được sắp xếp, upper_bound sẽ là một người bạn đồng hành đáng tin cậy, giúp bạn thực hiện các tác vụ tìm kiếm một cách hiệu quả.

Hãy cùng tìm hiểu xem upper_bound làm gì, nó khác biệt ra sao với các hàm tìm kiếm khác, và quan trọng nhất, thực hành sử dụng nó qua nhiều ví dụ cụ thể nhé!

`upper_bound`: Điểm Neo Cuối Cùng

Vậy, chính xác thì upper_bound làm gì?

Ngắn gọn mà nói, upper_bound là một hàm thuộc thư viện <algorithm> của C++. Nó hoạt động trên một dãy (range) đã được sắp xếp (như vector, list đã sắp xếp, mảng C++ thông thường, v.v.) và tìm kiếm vị trí của phần tử đầu tiên lớn hơn (strictly greater than) một giá trị cụ thể mà bạn cung cấp.

Điểm mấu chốt cần nhớ:

Yêu cầu dãy đã sắp xếp: upper_bound chỉ đảm bảo cho kết quả đúng khi dãy đầu vào đã được sắp xếp theo thứ tự không giảm (hoặc không tăng nếu sử dụng comparator ngược lại). Nếu dãy chưa sắp xếp, kết quả sẽ không xác định hoặc sai.
Trả về Iterator: Hàm không trả về giá trị tìm được (vì nó tìm vị trí của phần tử lớn hơn chứ không phải phần tử bằng). Thay vào đó, nó trả về một iterator trỏ đến vị trí đó.
Tìm kiếm phần tử lớn hơn: Đây là điểm khác biệt quan trọng nhất. upper_bound tìm phần tử đầu tiên nghiêm ngặt lớn hơn giá trị mục tiêu.

Hãy tưởng tượng bạn có một dãy số đã được sắp xếp: [1, 2, 3, 3, 3, 4, 5]. Nếu bạn tìm upper_bound cho giá trị 3:

Hàm sẽ đi qua 1, 2, 3, 3, 3.
Phần tử tiếp theo là 4, nó lớn hơn 3.
upper_bound sẽ trả về một iterator trỏ đến vị trí của số 4.

Nếu không có phần tử nào trong dãy lớn hơn giá trị mục tiêu, upper_bound sẽ trả về iterator trỏ đến vị trí ngay sau phần tử cuối cùng của dãy (hay còn gọi là end() iterator của container).

Cú pháp cơ bản

Hàm upper_bound có nhiều dạng quá tải, nhưng dạng phổ biến nhất là:

template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

first: Một iterator trỏ đến phần tử đầu tiên của dãy.
last: Một iterator trỏ đến vị trí ngay sau phần tử cuối cùng của dãy.
val: Giá trị mà bạn muốn tìm phần tử lớn hơn nó.

Ngoài ra, còn có dạng quá tải chấp nhận một comparator (hàm hoặc đối tượng hàm) để tùy chỉnh tiêu chí so sánh, hữu ích khi làm việc với các kiểu dữ liệu phức tạp hoặc muốn tìm kiếm trong dãy đã sắp xếp theo thứ tự giảm dần.

template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

comp: Đối tượng hàm hoặc lambda nhận hai tham số và trả về true nếu tham số thứ nhất được coi là nhỏ hơn tham số thứ hai theo tiêu chí sắp xếp của bạn.

Cơ chế hoạt động (khái niệm)

Mặc dù không được chỉ định cụ thể trong chuẩn, các cài đặt upper_bound thường sử dụng thuật toán tìm kiếm nhị phân (binary search). Điều này giải thích tại sao dãy đầu vào bắt buộc phải được sắp xếp và tại sao độ phức tạp thời gian của nó là logarit, tức là $O(\log n)$, nơi $n$ là số lượng phần tử trong dãy. Đây là một hiệu suất rất tốt, đặc biệt với các tập dữ liệu lớn.

Thực hành với các Ví dụ Minh Họa

Hãy cùng xem upper_bound hoạt động như thế nào qua các ví dụ C++ thực tế.

Ví dụ 1: Tìm upper_bound trong dãy số nguyên đơn giản

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

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

    // data đã được sắp xếp

    auto it = upper_bound(data.begin(), data.end(), value_to_find);

    cout << "Day du lieu: ";
    for (int x : data) {
        cout << x << " ";
    }
    cout << endl;

    cout << "Gia tri can tim upper_bound cho: " << value_to_find << endl;

    if (it == data.end()) {
        cout << "Khong co phan tu nao lon hon " << value_to_find << " trong day." << endl;
    } else {
        int index = distance(data.begin(), it);
        cout << "Phan tu dau tien lon hon " << value_to_find
                  << " la " << *it
                  << " tai vi tri (index): " << index << endl;
    }

    return 0;
}

Giải thích ví dụ 1:

Chúng ta có một vector<int> tên data đã được sắp xếp.
Chúng ta gọi upper_bound với data.begin(), data.end() và giá trị 30.
upper_bound sẽ tìm phần tử đầu tiên lớn hơn 30. Trong dãy [10, 20, 30, 30, 40, 50], phần tử đầu tiên lớn hơn 30 là 40.
Hàm trả về một iterator it trỏ đến vị trí của 40.
Chúng ta kiểm tra xem it có phải là data.end() không. Nếu không, chúng ta in ra giá trị mà iterator trỏ đến (*it) và tính toán vị trí (index) của nó bằng cách sử dụng distance(data.begin(), it). Kết quả in ra sẽ là 40 tại index 4.

Ví dụ 2: Trường hợp giá trị không tìm thấy (tất cả nhỏ hơn hoặc bằng)

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

int main() {
    vector<int> data = {10, 20, 30, 40, 50};
    int value_to_find = 60; // Lớn hơn tất cả các phần tử

    // data đã được sắp xếp

    auto it = upper_bound(data.begin(), data.end(), value_to_find);

    cout << "Day du lieu: ";
    for (int x : data) {
        cout << x << " ";
    }
    cout << endl;

    cout << "Gia tri can tim upper_bound cho: " << value_to_find << endl;

    if (it == data.end()) {
        cout << "Khong co phan tu nao lon hon " << value_to_find << " trong day." << endl;
        // it tro den vi tri ket thuc
        int index = distance(data.begin(), it);
        cout << "Iterator tro den vi tri index: " << index << " (ngoai pham vi hop le cua day)." << endl;

    } else {
        // Truong hop nay se khong xay ra voi gia tri = 60
        int index = distance(data.begin(), it);
        cout << "Phan tu dau tien lon hon " << value_to_find
                  << " la " << *it
                  << " tai vi tri (index): " << index << endl;
    }

    return 0;
}

Giải thích ví dụ 2:

Chúng ta tìm upper_bound cho giá trị 60.
Không có phần tử nào trong dãy [10, 20, 30, 40, 50] lớn hơn 60.
Theo định nghĩa, upper_bound sẽ trả về iterator trỏ đến vị trí data.end().
Câu lệnh if (it == data.end()) sẽ đúng, và chúng ta in ra thông báo tương ứng. Index tính bằng distance sẽ là kích thước của vector (trong trường hợp này là 5), cho thấy nó nằm ngoài phạm vi index hợp lệ từ 0 đến 4.

Ví dụ 3: Trường hợp giá trị không tìm thấy (tất cả lớn hơn hoặc bằng)

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

int main() {
    vector<int> data = {10, 20, 30, 40, 50};
    int value_to_find = 5; // Nhỏ hơn tất cả các phần tử

    // data đã được sắp xếp

    auto it = upper_bound(data.begin(), data.end(), value_to_find);

    cout << "Day du lieu: ";
    for (int x : data) {
        cout << x << " ";
    }
    cout << endl;

    cout << "Gia tri can tim upper_bound cho: " << value_to_find << endl;

    if (it == data.end()) {
        // Truong hop nay se khong xay ra voi gia tri = 5
        cout << "Khong co phan tu nao lon hon " << value_to_find << " trong day." << endl;
    } else {
        // Phan tu dau tien lon hon 5 la 10
        int index = distance(data.begin(), it);
        cout << "Phan tu dau tien lon hon " << value_to_find
                  << " la " << *it
                  << " tai vi tri (index): " << index << endl;
    }

    return 0;
}

Giải thích ví dụ 3:

Chúng ta tìm upper_bound cho giá trị 5.
Phần tử đầu tiên trong dãy [10, 20, 30, 40, 50] lớn hơn 5 là 10.
upper_bound sẽ trả về một iterator trỏ đến vị trí của 10.
Câu lệnh if (it == data.end()) sẽ sai. Chúng ta in ra giá trị *it (là 10) và index của nó (distance(data.begin(), it), là 0).

Ví dụ 4: Sử dụng upper_bound để đếm số lượng phần tử lớn hơn một giá trị

Vì upper_bound trả về iterator đến phần tử đầu tiên lớn hơn giá trị mục tiêu, chúng ta có thể dễ dàng tính toán số lượng các phần tử lớn hơn giá trị đó bằng cách tính khoảng cách từ iterator trả về đến end() iterator của dãy.

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

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

    // data đã được sắp xếp

    auto it = upper_bound(data.begin(), data.end(), value_to_find);

    cout << "Day du lieu: ";
    for (int x : data) {
        cout << x << " ";
    }
    cout << endl;

    cout << "Gia tri can tim upper_bound cho: " << value_to_find << endl;

    // So phan tu lon hon value_to_find la khoang cach tu 'it' den 'data.end()'
    int count_greater = distance(it, data.end());

    cout << "So luong phan tu lon hon " << value_to_find << " trong day la: " << count_greater << endl;

    return 0;
}

Giải thích ví dụ 4:

Chúng ta tìm upper_bound cho 30. it trỏ đến 40.
Khoảng cách từ it (trỏ đến 40) đến data.end() (sau 50) bao gồm các phần tử 40 và 50.
distance(it, data.end()) tính toán số lượng phần tử từ vị trí it đến cuối dãy. Kết quả là 2.
Đây chính là số lượng phần tử lớn hơn 30 trong dãy.

Ví dụ 5: Sử dụng upper_bound với kiểu dữ liệu tùy chỉnh và comparator

Giả sử chúng ta có một vector các cặp số và muốn tìm upper_bound dựa trên phần tử đầu tiên của cặp.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility> // Cần cho pair

int main() {
    vector<pair<int, char>> data = {{1, 'a'}, {3, 'b'}, {3, 'c'}, {5, 'd'}, {7, 'e'}};

    // data đã được sắp xếp dựa trên phan tu dau tien (int)

    int value_to_find = 3; // Muon tim cap dau tien co phan tu dau tien > 3

    // Sử dụng lambda làm comparator
    auto comparator = [](const pair<int, char>& element, int val) {
        return element.first < val; // So sanh phan tu dau tien cua pair voi 'val'
    };

    auto it = upper_bound(data.begin(), data.end(), value_to_find, comparator);

    cout << "Day du lieu (pair): ";
    for (const auto& p : data) {
        cout << "{" << p.first << "," << p.second << "} ";
    }
    cout << endl;

    cout << "Gia tri can tim upper_bound cho (phan tu dau tien): " << value_to_find << endl;

    if (it == data.end()) {
        cout << "Khong co cap nao co phan tu dau tien lon hon " << value_to_find << " trong day." << endl;
    } else {
        int index = distance(data.begin(), it);
        cout << "Cap dau tien co phan tu dau tien lon hon " << value_to_find
                  << " la {" << it->first << "," << it->second << "}"
                  << " tai vi tri (index): " << index << endl;
    }

    return 0;
}

Giải thích ví dụ 5:

Chúng ta có một vector các pair<int, char>, đã được sắp xếp dựa trên giá trị int đầu tiên của mỗi cặp.
Chúng ta muốn tìm cặp đầu tiên mà phần tử int đầu tiên của nó lớn hơn 3.
upper_bound cần biết cách so sánh một pair<int, char> với một int. Chúng ta cung cấp một lambda function làm comparator. Lambda này nhận một cặp (element) và giá trị int (val), và trả về true nếu element.first nhỏ hơn val. Đây là tiêu chí so sánh phù hợp với cách upper_bound sử dụng comparator (tìm kiếm vị trí không lớn hơn giá trị, sau đó bước qua).
upper_bound sử dụng comparator này để tìm vị trí. Cặp đầu tiên có phần tử đầu tiên lớn hơn 3 là {5, 'd'}.
it trỏ đến {5, 'd'}. Index của nó là 3.

Lưu ý quan trọng khi sử dụng `upper_bound`

LUÔN ĐẢM BẢO DÃY ĐƯỢC SẮP XẾP: Tôi không thể nhấn mạnh điều này đủ. Nếu dãy không được sắp xếp, kết quả của upper_bound sẽ không đúng. Sử dụng sort trước khi gọi upper_bound nếu cần.
Kết quả là iterator: Hãy nhớ rằng upper_bound trả về một iterator. Để truy cập giá trị, bạn phải dereference iterator (*it). Để biết vị trí (index), bạn sử dụng distance.
Tìm kiếm nghiêm ngặt lớn hơn: Phân biệt rõ upper_bound với lower_bound (tìm kiếm phần tử đầu tiên không nhỏ hơn). upper_bound "đẩy" bạn đến vị trí ngay sau nhóm các phần tử bằng giá trị mục tiêu (nếu có), để tìm phần tử lớn hơn đầu tiên.

upper_bound là một phần tử mạnh mẽ của STL, rất hữu ích khi bạn cần tìm kiếm hiệu quả trên dữ liệu đã sắp xếp, đặc biệt là khi bạn quan tâm đến ranh giới phía trên của các phần tử bằng hoặc nhỏ hơn một giá trị nào đó. Bằng cách hiểu rõ nó hoạt động như thế nào và thực hành qua các ví dụ, bạn sẽ có thêm một công cụ đắc lực trong hộp công cụ lập trình C++ của mình.

Comments

There are no comments at the moment.