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ớ:

  1. 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.
  2. 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í đó.
  3. 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>

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

    auto itr = upper_bound(v.begin(), v.end(), gt);

    cout << "Day du lieu: ";
    for (int e : v) {
        cout << e << " ";
    }
    cout << endl;

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

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

    return 0;
}

Output:

Day du lieu: 10 20 30 30 40 50 
Gia tri can tim upper_bound cho: 30
Phan tu dau tien lon hon 30 la 40 tai vi tri (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> v = {10, 20, 30, 40, 50};
    int gt = 60;

    auto itr = upper_bound(v.begin(), v.end(), gt);

    cout << "Day du lieu: ";
    for (int e : v) {
        cout << e << " ";
    }
    cout << endl;

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

    if (itr == v.end()) {
        cout << "Khong co phan tu nao lon hon " << gt << " trong day." << endl;
        int viTri = distance(v.begin(), itr);
        cout << "Iterator tro den vi tri index: " << viTri << " (ngoai pham vi hop le cua day)." << endl;
    } else {
        int viTri = distance(v.begin(), itr);
        cout << "Phan tu dau tien lon hon " << gt
                  << " la " << *itr
                  << " tai vi tri (index): " << viTri << endl;
    }

    return 0;
}

Output:

Day du lieu: 10 20 30 40 50 
Gia tri can tim upper_bound cho: 60
Khong co phan tu nao lon hon 60 trong day.
Iterator tro den vi tri index: 5 (ngoai pham vi hop le cua day).

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> v = {10, 20, 30, 40, 50};
    int gt = 5;

    auto itr = upper_bound(v.begin(), v.end(), gt);

    cout << "Day du lieu: ";
    for (int e : v) {
        cout << e << " ";
    }
    cout << endl;

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

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

    return 0;
}

Output:

Day du lieu: 10 20 30 40 50 
Gia tri can tim upper_bound cho: 5
Phan tu dau tien lon hon 5 la 10 tai vi tri (index): 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> v = {10, 20, 30, 30, 40, 50};
    int gt = 30;

    auto itr = upper_bound(v.begin(), v.end(), gt);

    cout << "Day du lieu: ";
    for (int e : v) {
        cout << e << " ";
    }
    cout << endl;

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

    int demLonHon = distance(itr, v.end());

    cout << "So luong phan tu lon hon " << gt << " trong day la: " << demLonHon << endl;

    return 0;
}

Output:

Day du lieu: 10 20 30 30 40 50 
Gia tri can tim upper_bound cho: 30
So luong phan tu lon hon 30 trong day la: 2

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>

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

    auto soSanh = [](const pair<int, char>& p, int g) {
        return p.first < g;
    };

    auto itr = upper_bound(ds.begin(), ds.end(), gt, soSanh);

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

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

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

    return 0;
}

Output:

Day du lieu (pair): {1,a} {3,b} {3,c} {5,d} {7,e} 
Gia tri can tim upper_bound cho (phan tu dau tien): 3
Cap dau tien co phan tu dau tien lon hon 3 la {5,d} tai vi tri (index): 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.