Upper bound và Lower bound cho vector giảm dần trong C++

Trong bài viết này, chúng ta sẽ thảo luận về vector::upper_bound() và vector::lower_bound() cho mảng được sắp xếp theo thứ tự không tăng dần (non-increasing) trong C++ STL.

Vector tương tự như mảng động; chúng có khả năng tự thay đổi kích thước khi giá trị được chèn vào hoặc xóa khỏi container.

Trong Vector sắp xếp giảm dần:

• Lower bound trả về iterator trỏ đến phần tử đầu tiên trong phạm vi không lớn hơn (≤) giá trị cho trước.
• Upper bound trả về iterator trỏ đến phần tử đầu tiên trong phạm vi nhỏ hơn (<) giá trị cho trước.

Ví dụ minh họa

Input

30 30 30 20 20 20 10 10

Output

Lower bound of 20 = 3
Upper bound of 20 = 6

Giải thích: Với giá trị 20, lower_bound trỏ đến vị trí 3 (phần tử 20 đầu tiên), upper_bound trỏ đến vị trí 6 (phần tử 10 đầu tiên - nhỏ hơn 20).

Input

9 9 8 8 8 7 7 7 6 6 6 6

Output

Lower bound of 7 = 5
Upper bound of 7 = 8

Giá trị trả về

Trả về iterator trỏ đến phần tử đầu tiên của phạm vi (lower_bound) và iterator trỏ đến phần tử cuối cùng của phạm vi (upper_bound).

Cách tiếp cận

1. Khởi tạo vector.
2. Sắp xếp vector theo thứ tự không tăng dần (sử dụng greater<int>()).
3. Tìm lower bound bằng lower_bound với comparator greater<int>().
4. Tìm upper bound bằng upper_bound với comparator greater<int>().
5. In kết quả.

Lưu ý quan trọng: Vector bắt buộc phải được sắp xếp mới có thể tìm lower/upper bound chính xác. Nếu vector chưa sắp xếp, kết quả sẽ không đúng.

Ví dụ code hoàn chỉnh

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int vect[] = {13, 13, 13, 16, 16, 16, 17, 17, 17, 17, 18, 18};
    vector<int> v(vect, vect + 12);
    
    // Sắp xếp giảm dần
    sort(v.begin(), v.end(), greater<int>());
    
    cout << "Sorted Vector: ";
    for (auto i : v) cout << i << " ";
    cout << endl;
    
    // Tìm lower/upper bound cho giá trị 17
    auto low = lower_bound(v.begin(), v.end(), 17, greater<int>());
    auto up = upper_bound(v.begin(), v.end(), 17, greater<int>());
    
    cout << "Lower bound = " << (low - v.begin()) << endl;
    cout << "Upper bound = " << (up - v.begin()) << endl;
    
    return 0;
}

Kết quả

Sorted Vector: 18 18 17 17 17 17 16 16 16 13 13 13
Lower bound = 2
Upper bound = 6

Ví dụ thứ 2 (sắp xếp tăng dần để so sánh)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int vect[] = {5, 5, 5, 5, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10};
    vector<int> v(vect, vect + 16);
    
    // Sắp xếp giảm dần
    sort(v.begin(), v.end(), greater<int>());
    
    cout << "Sorted Vector: ";
    for (auto i : v) cout << i << " ";
    cout << endl;
    
    auto low = lower_bound(v.begin(), v.end(), 8, greater<int>());
    auto up = upper_bound(v.begin(), v.end(), 8, greater<int>());
    
    cout << "Lower bound = " << (low - v.begin()) << endl;
    cout << "Upper bound = " << (up - v.begin()) << endl;
    
    return 0;
}

Kết quả

Sorted Vector: 10 10 9 9 9 8 8 8 8 7 7 7 5 5 5 5
Lower bound = 5
Upper bound = 9