Bài 21.4: Hàm lower_bound và upper_bound trong C++

Trong thế giới lập trình C++, việc xử lý và tìm kiếm dữ liệu hiệu quả là chìa khóa để xây dựng các ứng dụng mạnh mẽ và nhanh chóng. Đặc biệt, khi làm việc với các dãy dữ liệu đã được sắp xếp, chúng ta có thể tận dụng các thuật toán tìm kiếm tối ưu thay vì tìm kiếm tuyến tính (duyệt từng phần tử một). Thư viện chuẩn C++ (STL) cung cấp cho chúng ta hai công cụ cực kỳ hữu ích dựa trên nguyên tắc tìm kiếm nhị phân (binary search) cho mục đích này: hàm lower_bound và upper_bound.

Hai hàm này thoạt nhìn có vẻ tương tự nhau, nhưng chúng phục vụ các mục đích hơi khác biệt và khi kết hợp lại, chúng mang lại sức mạnh đáng kinh ngạc trong việc xử lý các dãy đã sắp xếp. Hãy cùng đi sâu vào tìm hiểu từng hàm một nhé!

lower_bound: Điểm Khởi Đầu Của Sự Xuất Hiện (hoặc hơn thế)

Hàm lower_bound được sử dụng để tìm kiếm vị trí đầu tiên trong một dãy đã sắp xếp mà phần tử tại đó không nhỏ hơn (nghĩa là lớn hơn hoặc bằng) một giá trị cụ thể mà bạn đang tìm kiếm.

Định nghĩa và Cú pháp cơ bản:

lower_bound nhận vào ba đối số chính:

  1. first: Một iterator trỏ đến phần tử đầu tiên của dãy.
  2. last: Một iterator trỏ đến vị trí ngay sau phần tử cuối cùng của dãy.
  3. value: Giá trị mà bạn muốn tìm kiếm.

Nó trả về một iterator trỏ đến phần tử đầu tiên trong dãy trong khoảng [first, last) mà không nhỏ hơn value. Nếu không có phần tử nào như vậy (nghĩa là tất cả các phần tử đều nhỏ hơn value), nó sẽ trả về iterator last.

Cú pháp (phiên bản đơn giản nhất):

iterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

(Lưu ý: Có các phiên bản quá tải khác chấp nhận hàm so sánh tùy chỉnh)

Ví dụ 1: Tìm kiếm giá trị tồn tại

Hãy xem một ví dụ đơn giản với một vector đã sắp xếp:

#include <iostream>
#include <vector>
#include <algorithm> // Bao gom lower_bound
#include <iterator>  // Bao gom distance

int main() {
    // Vector da duoc sap xep
    vector<int> data = {10, 20, 30, 30, 40, 50};
    int value_to_find = 30;

    // Goi lower_bound
    auto it_lower = lower_bound(data.begin(), data.end(), value_to_find);

    // Kiem tra xem iterator co hop le khong (khac data.end())
    if (it_lower != data.end()) {
        cout << "lower_bound cho gia tri " << value_to_find
                  << " la phan tu " << *it_lower // Dereference iterator de lay gia tri
                  << " tai chi so: " << distance(data.begin(), it_lower) << endl; // Tinh chi so
    } else {
        // Truong hop nay xay ra khi value_to_find lon hon tat ca cac phan tu trong day
        cout << "Khong tim thay phan tu >= " << value_to_find << " trong day." << endl;
    }

    return 0;
}

Giải thích:

Trong ví dụ này, vector data chứa các số đã sắp xếp. Chúng ta tìm kiếm giá trị 30. lower_bound(data.begin(), data.end(), 30) sẽ duyệt tìm trong dãy [10, 20, 30, 30, 40, 50). Nó tìm kiếm phần tử đầu tiên không nhỏ hơn 30.

  • 10 < 30 (nhỏ hơn)
  • 20 < 30 (nhỏ hơn)
  • 30 >= 30 (không nhỏ hơn) -> Đây là phần tử đầu tiên thỏa mãn!

Vì vậy, it_lower sẽ trỏ đến phần tử 30 đầu tiên (tại chỉ số 2). Output sẽ là: lower_bound cho gia tri 30 la phan tu 30 tai chi so: 2

Ví dụ 2: Tìm kiếm giá trị không tồn tại (nhỏ hơn hoặc nằm giữa)

Điều gì xảy ra nếu giá trị tìm kiếm không có mặt trong 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_1 = 25; // Gia tri nam giua 20 va 30
    int value_to_find_2 = 5;  // Gia tri nho hon tat ca

    // Tim kiem 25
    auto it_lower_1 = lower_bound(data.begin(), data.end(), value_to_find_1);

    if (it_lower_1 != data.end()) {
        cout << "lower_bound cho gia tri " << value_to_find_1
                  << " la phan tu " << *it_lower_1
                  << " tai chi so: " << distance(data.begin(), it_lower_1) << endl;
    } // Else case khong xay ra vi it_lower_1 != data.end()

    // Tim kiem 5
    auto it_lower_2 = lower_bound(data.begin(), data.end(), value_to_find_2);

     if (it_lower_2 != data.end()) {
        cout << "lower_bound cho gia tri " << value_to_find_2
                  << " la phan tu " << *it_lower_2
                  << " tai chi so: " << distance(data.begin(), it_lower_2) << endl;
     } else {
         // Truong hop nay chi xay ra neu value_to_find_2 > tat ca phan tu (khong phai truong hop nay)
         cout << "lower_bound cho gia tri " << value_to_find_2
                   << " tra ve end()." << endl;
     }

    return 0;
}

Giải thích:

  • Đối với value_to_find_1 = 25: lower_bound tìm phần tử đầu tiên >= 25. Đó chính là số 30 tại chỉ số 2. Output: lower_bound cho gia tri 25 la phan tu 30 tai chi so: 2
  • Đối với value_to_find_2 = 5: lower_bound tìm phần tử đầu tiên >= 5. Đó chính là số 10 tại chỉ số 0 (phần tử đầu tiên). Output: lower_bound cho gia tri 5 la phan tu 10 tai chi so: 0

Lưu ý rằng lower_bound sẽ chỉ trả về data.end() nếu giá trị tìm kiếm lớn hơn tất cả các phần tử trong dãy.

upper_bound: Điểm Kết Thúc Của Sự Xuất Hiện (hoặc sau đó)

Hàm upper_bound được sử dụng để tìm kiếm vị trí đầu tiên trong một dãy đã sắp xếp mà phần tử tại đó lớn hơn một giá trị cụ thể mà bạn đang tìm kiếm.

Định nghĩa và Cú pháp cơ bản:

upper_bound cũng nhận ba đối số tương tự: first, last, và value.

Nó trả về một iterator trỏ đến phần tử đầu tiên trong dãy trong khoảng [first, last) mà lớn hơn value. Nếu không có phần tử nào như vậy (nghĩa là tất cả các phần tử đều nhỏ hơn hoặc bằng value), nó sẽ trả về iterator last.

Cú pháp (phiên bản đơn giản nhất):

iterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

(Lưu ý: Cũng có các phiên bản quá tải khác chấp nhận hàm so sánh tùy chỉnh)

Ví dụ 1: Tìm kiếm giá trị tồn tại

Sử dụng lại vector từ ví dụ trước:

#include <iostream>
#include <vector>
#include <algorithm> // Bao gom upper_bound
#include <iterator>  // Bao gom distance

int main() {
    // Vector da duoc sap xep
    vector<int> data = {10, 20, 30, 30, 40, 50};
    int value_to_find = 30;

    // Goi upper_bound
    auto it_upper = upper_bound(data.begin(), data.end(), value_to_find);

    // Kiem tra xem iterator co hop le khong (khac data.end())
    if (it_upper != data.end()) {
        cout << "upper_bound cho gia tri " << value_to_find
                  << " la phan tu " << *it_upper // Dereference iterator de lay gia tri
                  << " tai chi so: " << distance(data.begin(), it_upper) << endl; // Tinh chi so
    } else {
         // Truong hop nay xay ra khi value_to_find >= tat ca cac phan tu trong day
        cout << "Khong tim thay phan tu > " << value_to_find << " trong day." << endl;
    }

    return 0;
}

Giải thích:

Chúng ta tìm kiếm giá trị 30. upper_bound tìm kiếm phần tử đầu tiên lớn hơn 30.

  • 10 < 30 (nhỏ hơn hoặc bằng)
  • 20 < 30 (nhỏ hơn hoặc bằng)
  • 30 <= 30 (nhỏ hơn hoặc bằng)
  • 30 <= 30 (nhỏ hơn hoặc bằng)
  • 40 > 30 (lớn hơn) -> Đây là phần tử đầu tiên thỏa mãn!

Vì vậy, it_upper sẽ trỏ đến phần tử 40 (tại chỉ số 4). Output sẽ là: upper_bound cho gia tri 30 la phan tu 40 tai chi so: 4

Ví dụ 2: Tìm kiếm giá trị không tồn tại (lớn hơn hoặc nằm giữa)
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    vector<int> data = {10, 20, 30, 30, 40, 50};
    int value_to_find_1 = 35; // Gia tri nam giua 30 va 40
    int value_to_find_2 = 60; // Gia tri lon hon tat ca

    // Tim kiem 35
    auto it_upper_1 = upper_bound(data.begin(), data.end(), value_to_find_1);

    if (it_upper_1 != data.end()) {
        cout << "upper_bound cho gia tri " << value_to_find_1
                  << " la phan tu " << *it_upper_1
                  << " tai chi so: " << distance(data.begin(), it_upper_1) << endl;
    } // Else case khong xay ra

    // Tim kiem 60
    auto it_upper_2 = upper_bound(data.begin(), data.end(), value_to_find_2);

     if (it_upper_2 != data.end()) {
        // Truong hop nay chi xay ra neu value_to_find_2 < tat ca phan tu (khong phai truong hop nay)
        cout << "upper_bound cho gia tri " << value_to_find_2
                   << " la phan tu " << *it_upper_2 << "..." << endl;
     } else {
        // Truong hop nay xay ra khi value_to_find_2 >= tat ca cac phan tu
        cout << "upper_bound cho gia tri " << value_to_find_2
                  << " tra ve end(), nghia la khong co phan tu > "
                  << value_to_find_2 << " trong day." << endl;
     }

    return 0;
}

Giải thích:

  • Đối với value_to_find_1 = 35: upper_bound tìm phần tử đầu tiên > 35. Đó chính là số 40 tại chỉ số 4. Output: upper_bound cho gia tri 35 la phan tu 40 tai chi so: 4
  • Đối với value_to_find_2 = 60: upper_bound tìm phần tử đầu tiên > 60. Không có phần tử nào như vậy trong dãy. Do đó, nó trả về data.end(). Output: upper_bound cho gia tri 60 tra ve end(), nghia la khong co phan tu > 60 trong day.

Lưu ý rằng upper_bound sẽ trả về data.begin() nếu giá trị tìm kiếm nhỏ hơn tất cả các phần tử trong dãy (vì phần tử đầu tiên đã lớn hơn giá trị đó).

Sức Mạnh Tổng Hợp: Tìm Toàn Bộ Sự Xuất Hiện

Đây là lúc sự kết hợp của lower_bound và upper_bound thực sự tỏa sáng! Khi sử dụng cùng một giá trị tìm kiếm trên một dãy đã sắp xếp:

  • lower_bound(first, last, value) trả về iterator đến phần tử đầu tiên >= value.
  • upper_bound(first, last, value) trả về iterator đến phần tử đầu tiên > value.

Điều này có nghĩa là tất cả các phần tử có giá trị bằng value sẽ nằm trong khoảng iterator [lower_bound_iterator, upper_bound_iterator). Đây là một khoảng nửa mở (half-open range), bao gồm điểm bắt đầu (lower_bound_iterator) nhưng không bao gồm điểm kết thúc (upper_bound_iterator).

Chúng ta có thể sử dụng khoảng này để:

  1. Kiểm tra xem giá trị có tồn tại trong dãy hay không.
  2. Đếm số lần xuất hiện của giá trị đó.
  3. Lặp qua tất cả các lần xuất hiện của giá trị đó.
Ví dụ: Tìm tất cả các lần xuất hiện của một giá trị
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator> // Bao gom distance

int main() {
    // Vector co nhieu phan tu trung lap va da sap xep
    vector<int> data = {10, 20, 30, 30, 30, 40, 50};
    int value_to_find = 30;

    // Tim lower_bound va upper_bound
    auto it_lower = lower_bound(data.begin(), data.end(), value_to_find);
    auto it_upper = upper_bound(data.begin(), data.end(), value_to_find);

    // Kiem tra xem gia tri co ton tai it nhat mot lan khong
    // lower_bound khac end() va phan tu no tro den phai bang value_to_find
    // (it_upper == it_lower cung co nghia la khong tim thay hoac chi tim thay diem chen)
    if (it_lower != data.end() && *it_lower == value_to_find) {
        cout << "Gia tri " << value_to_find << " xuat hien tai cac chi so: ";
        for (auto it = it_lower; it != it_upper; ++it) {
            cout << distance(data.begin(), it) << " ";
        }
        cout << endl;

        // Dem so lan xuat hien bang cach tinh khoang cach giua hai iterator
        cout << "Tong so lan xuat hien cua gia tri " << value_to_find << " la: "
                  << distance(it_lower, it_upper) << endl;

    } else {
        cout << "Gia tri " << value_to_find << " khong tim thay trong day." << endl;
    }

    // Vi du voi gia tri khong ton tai
    int non_existent_value = 25;
     auto it_lower_non = lower_bound(data.begin(), data.end(), non_existent_value);
     auto it_upper_non = upper_bound(data.begin(), data.end(), non_existent_value);

     if (it_lower_non != data.end() && *it_lower_non == non_existent_value) { // Dieu kien nay se sai
          // Se khong bao gio vao day
     } else {
         // it_lower_non se tro den phan tu >= 25 dau tien (la 30 tai chi so 2)
         // it_upper_non se tro den phan tu > 25 dau tien (cung la 30 tai chi so 2)
         // Khoang [it_lower_non, it_upper_non) rong, distance = 0
         cout << "Gia tri " << non_existent_value << " khong tim thay trong day (su dung lower/upper bound)." << endl;
         cout << "So lan xuat hien cua " << non_existent_value << " la: "
                   << distance(it_lower_non, it_upper_non) << endl; // Se in ra 0
     }


    return 0;
}

Giải thích:

  • Với value_to_find = 30, it_lower trỏ đến 30 đầu tiên (chỉ số 2), và it_upper trỏ đến 40 (chỉ số 5). Khoảng [it_lower, it_upper) bao gồm các phần tử tại chỉ số 2, 3, 4, đó chính là ba số 30.
  • Vòng lặp for (auto it = it_lower; it != it_upper; ++it) sẽ duyệt qua chính xác các phần tử này.
  • distance(it_lower, it_upper) tính số lượng phần tử trong khoảng đó, cho ra kết quả là 3.
  • Đối với non_existent_value = 25, it_lower_non trỏ đến 30 đầu tiên (chỉ số 2), và it_upper_non cũng trỏ đến 30 đầu tiên (chỉ số 2). Khoảng [it_lower_non, it_upper_non) là rỗng. Điều kiện *it_lower_non == non_existent_value (tức là *it_lower_non == 25) là sai, nên chúng ta biết rằng giá trị 25 không tồn tại. distance(it_lower_non, it_upper_non) trả về 0, cho thấy không có lần xuất hiện nào.

Mẹo: equal_range(first, last, value) là một hàm tiện lợi trong <algorithm> thực hiện chính xác việc gọi cả lower_bound và upper_bound và trả về một pair chứa cả hai iterator.

Sử Dụng Hàm So Sánh Tùy Chỉnh

Cả lower_bound và upper_bound đều có phiên bản quá tải cho phép bạn cung cấp một hàm so sánh tùy chỉnh thay vì sử dụng toán tử < mặc định. Điều này cực kỳ hữu ích khi bạn làm việc với các kiểu dữ liệu phức tạp hoặc khi dãy của bạn được sắp xếp theo một tiêu chí khác (ví dụ: giảm dần).

Hàm so sánh này thường là một binary predicate (một hàm nhận hai đối số và trả về bool), được sử dụng để xác định mối quan hệ "nhỏ hơn" giữa hai phần tử.

Cú pháp với hàm so sánh:

iterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
iterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

Ở đây, comp(a, b) trả về true nếu a được coi là "nhỏ hơn" b theo tiêu chí sắp xếp của bạn.

Ví dụ: Sử dụng với vector sắp xếp giảm dần

Nếu vector được sắp xếp giảm dần, chúng ta cần sử dụng hàm so sánh như greater<int>().

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <functional> // Bao gom greater

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

    // Khi dung greater<int>():
    // lower_bound tim phan tu dau tien ma !(phan tu > value_to_find), tuc la phan tu <= value_to_find
    // upper_bound tim phan tu dau tien ma (phan tu > value_to_find), tuc la phan tu < value_to_find

    auto it_lower = lower_bound(data.begin(), data.end(), value_to_find, greater<int>());
    auto it_upper = upper_bound(data.begin(), data.end(), value_to_find, greater<int>());

    // Kiem tra su ton tai va in ra cac chi so
     if (it_lower != data.end() && *it_lower == value_to_find) {
        cout << "Gia tri " << value_to_find << " xuat hien tai cac chi so (giam dan): ";
        for (auto it = it_lower; it != it_upper; ++it) {
            cout << distance(data.begin(), it) << " ";
        }
        cout << endl;

        cout << "Tong so lan xuat hien (giam dan): "
                  << distance(it_lower, it_upper) << endl;

     } else {
        cout << "Gia tri " << value_to_find << " khong tim thay trong day (giam dan)." << endl;
     }

    return 0;
}

Giải thích:

Vector data bây giờ sắp xếp giảm dần. Chúng ta sử dụng greater<int>() làm hàm so sánh.

  • lower_bound với greater<int>() tìm kiếm phần tử đầu tiên x sao cho greater<int>()(x, value_to_find) là false. Điều này có nghĩa là !(x > value_to_find), tương đương với x <= value_to_find. Phần tử đầu tiên <= 30 trong dãy {50, 40, 30, 30, 20, 10} là 30 tại chỉ số 2.
  • upper_bound với greater<int>() tìm kiếm phần tử đầu tiên x sao cho greater<int>()(x, value_to_find) là true. Điều này có nghĩa là x > value_to_find, tương đương với x < value_to_find (theo nghĩa thông thường). Phần tử đầu tiên < 30 trong dãy {50, 40, 30, 30, 20, 10} là 20 tại chỉ số 4.

Khoảng [it_lower, it_upper) vẫn bao gồm các phần tử có giá trị bằng value_to_find trong dãy đã sắp xếp theo tiêu chí greater<int>(). Output sẽ hiển thị các chỉ số 2, 3.

Việc sử dụng hàm so sánh tùy chỉnh giúp lower_bound và upper_bound trở nên linh hoạt hơn rất nhiều, cho phép bạn áp dụng chúng cho các cấu trúc dữ liệu và tiêu chí sắp xếp đa dạng.

Lưu ý quan trọng: lower_bound và upper_bound chỉ hoạt động chính xác trên các dãy đã được sắp xếp dựa trên cùng tiêu chí so sánh mà bạn cung cấp (hoặc toán tử < mặc định nếu không cung cấp comparator). Nếu dãy không được sắp xếp, kết quả sẽ không xác định.

Cả hai hàm này đều có độ phức tạp thời gian là O(log N) đối với các iterator truy cập ngẫu nhiên (như của vector, deque, array) và O(N) đối với các iterator tiến (forward iterators, như của list), trong đó N là số lượng phần tử trong dãy. Hiệu suất Logarit là cực kỳ nhanh cho các dãy lớn, làm cho chúng trở thành lựa chọn lý tưởng cho các bài toán tìm kiếm trên dữ liệu đã sắp xếp.

Comments

There are no comments at the moment.