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

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

int main() {
    using namespace std;
    vector<int> du_lieu = {10, 20, 30, 30, 40, 50};
    int gt_tim = 30;

    auto it_duoi = lower_bound(du_lieu.begin(), du_lieu.end(), gt_tim);

    if (it_duoi != du_lieu.end()) {
        cout << "lower_bound cho gia tri " << gt_tim
                  << " la phan tu " << *it_duoi
                  << " tai chi so: " << distance(du_lieu.begin(), it_duoi) << endl;
    } else {
        cout << "Khong tim thay phan tu >= " << gt_tim << " trong day." << endl;
    }

    return 0;
}

Output:

lower_bound cho gia tri 30 la phan tu 30 tai chi so: 2

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() {
    using namespace std;
    vector<int> du_lieu = {10, 20, 30, 30, 40, 50};
    int gt_tim1 = 25;
    int gt_tim2 = 5;

    auto it_duoi1 = lower_bound(du_lieu.begin(), du_lieu.end(), gt_tim1);

    if (it_duoi1 != du_lieu.end()) {
        cout << "lower_bound cho gia tri " << gt_tim1
                  << " la phan tu " << *it_duoi1
                  << " tai chi so: " << distance(du_lieu.begin(), it_duoi1) << endl;
    }

    auto it_duoi2 = lower_bound(du_lieu.begin(), du_lieu.end(), gt_tim2);

     if (it_duoi2 != du_lieu.end()) {
        cout << "lower_bound cho gia tri " << gt_tim2
                  << " la phan tu " << *it_duoi2
                  << " tai chi so: " << distance(du_lieu.begin(), it_duoi2) << endl;
     } else {
         cout << "lower_bound cho gia tri " << gt_tim2
                   << " tra ve end()." << endl;
     }

    return 0;
}

Output:

lower_bound cho gia tri 25 la phan tu 30 tai chi so: 2
lower_bound cho gia tri 5 la phan tu 10 tai chi so: 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>
#include <iterator>

int main() {
    using namespace std;
    vector<int> du_lieu = {10, 20, 30, 30, 40, 50};
    int gt_tim = 30;

    auto it_tren = upper_bound(du_lieu.begin(), du_lieu.end(), gt_tim);

    if (it_tren != du_lieu.end()) {
        cout << "upper_bound cho gia tri " << gt_tim
                  << " la phan tu " << *it_tren
                  << " tai chi so: " << distance(du_lieu.begin(), it_tren) << endl;
    } else {
        cout << "Khong tim thay phan tu > " << gt_tim << " trong day." << endl;
    }

    return 0;
}

Output:

upper_bound cho gia tri 30 la phan tu 40 tai chi so: 4

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() {
    using namespace std;
    vector<int> du_lieu = {10, 20, 30, 30, 40, 50};
    int gt_tim1 = 35;
    int gt_tim2 = 60;

    auto it_tren1 = upper_bound(du_lieu.begin(), du_lieu.end(), gt_tim1);

    if (it_tren1 != du_lieu.end()) {
        cout << "upper_bound cho gia tri " << gt_tim1
                  << " la phan tu " << *it_tren1
                  << " tai chi so: " << distance(du_lieu.begin(), it_tren1) << endl;
    }

    auto it_tren2 = upper_bound(du_lieu.begin(), du_lieu.end(), gt_tim2);

     if (it_tren2 != du_lieu.end()) {
        cout << "upper_bound cho gia tri " << gt_tim2
                   << " la phan tu " << *it_tren2 << "..." << endl;
     } else {
        cout << "upper_bound cho gia tri " << gt_tim2
                  << " tra ve end(), nghia la khong co phan tu > "
                  << gt_tim2 << " trong day." << endl;
     }

    return 0;
}

Output:

upper_bound cho gia tri 35 la phan tu 40 tai chi so: 4
upper_bound cho gia tri 60 tra ve end(), nghia la khong co phan tu > 60 trong day.

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>

int main() {
    using namespace std;
    vector<int> du_lieu = {10, 20, 30, 30, 30, 40, 50};
    int gt_tim = 30;

    auto it_duoi = lower_bound(du_lieu.begin(), du_lieu.end(), gt_tim);
    auto it_tren = upper_bound(du_lieu.begin(), du_lieu.end(), gt_tim);

    if (it_duoi != du_lieu.end() && *it_duoi == gt_tim) {
        cout << "Gia tri " << gt_tim << " xuat hien tai cac chi so: ";
        for (auto it = it_duoi; it != it_tren; ++it) {
            cout << distance(du_lieu.begin(), it) << " ";
        }
        cout << endl;

        cout << "Tong so lan xuat hien cua gia tri " << gt_tim << " la: "
                  << distance(it_duoi, it_tren) << endl;

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

    int gt_khong_co = 25;
    auto it_duoi_kc = lower_bound(du_lieu.begin(), du_lieu.end(), gt_khong_co);
    auto it_tren_kc = upper_bound(du_lieu.begin(), du_lieu.end(), gt_khong_co);

    if (it_duoi_kc != du_lieu.end() && *it_duoi_kc == gt_khong_co) {
         // This block will not be entered
    } else {
        cout << "Gia tri " << gt_khong_co << " khong tim thay trong day (su dung lower/upper bound)." << endl;
        cout << "So lan xuat hien cua " << gt_khong_co << " la: "
                   << distance(it_duoi_kc, it_tren_kc) << endl;
    }

    return 0;
}

Output:

Gia tri 30 xuat hien tai cac chi so: 2 3 4 
Tong so lan xuat hien cua gia tri 30 la: 3
Gia tri 25 khong tim thay trong day (su dung lower/upper bound).
So lan xuat hien cua 25 la: 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>

int main() {
    using namespace std;
    vector<int> du_lieu = {50, 40, 30, 30, 20, 10};
    int gt_tim = 30;

    auto it_duoi = lower_bound(du_lieu.begin(), du_lieu.end(), gt_tim, greater<int>());
    auto it_tren = upper_bound(du_lieu.begin(), du_lieu.end(), gt_tim, greater<int>());

    if (it_duoi != du_lieu.end() && *it_duoi == gt_tim) {
        cout << "Gia tri " << gt_tim << " xuat hien tai cac chi so (giam dan): ";
        for (auto it = it_duoi; it != it_tren; ++it) {
            cout << distance(du_lieu.begin(), it) << " ";
        }
        cout << endl;

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

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

    return 0;
}

Output:

Gia tri 30 xuat hien tai cac chi so (giam dan): 2 3 
Tong so lan xuat hien (giam dan): 2

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.