Hàm upper_bound() trong C++ được sử dụng để trả về phần tử kế tiếp mà lớn hơn giá trị cần tìm. Nếu không tìm thấy sẽ trả về vị trí cuối cùng+1 của mảng. Độ phức tạp hàm upper_bound() là O(logn), n là số lượng phần tử trong mảng.

Ví dụ:

• Mảng [10, 20, 30, 30, 30, 40, 50], Giá trị cần tìm 30. Thì hàm upper_bound sẽ trả về vị trí 5.
• Mảng [10, 20, 30, 30, 30, 40, 50], Giá trị cần tìm 35. Thì hàm upper_bound sẽ trả về vị trí 5.
• Mảng [10, 20, 30, 30, 30, 40, 50], Giá trị cần tìm 55. Thì hàm upper_bound sẽ trả về vị trí 7 (7 = vị trí cuối cùng + 1), có nghĩa là phần tử 55 không tồn tại trong mảng.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    // Input vector
    vector<int> v{ 10, 20, 30, 30, 30, 40, 50 };

    auto pos_30 = upper_bound(v.begin(), v.end(), 30);
    auto pos_35 = upper_bound(v.begin(), v.end(), 35);
    auto pos_55 = upper_bound(v.begin(), v.end(), 55);

    cout << "Phan tu 30 nam o vi tri: " << (pos_30 - v.begin()) << endl; // 5
    cout << "Phan tu 35 nam o vi tri: " << (pos_35 - v.begin()) << endl; // 5
    cout << "Phan tu 55 nam o vi tri: " << (pos_55 - v.begin());         // 7

    return 0;
}