std::upper_bound

#include <algorithm>

// So sánh bằng toán tử <
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                     const T& val);

// Sử dụng hàm so sánh tùy chỉnh
template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                     const T& val, Compare comp);

Tìm vị trí đầu tiên trong một phạm vi (range) đã được sắp xếp mà có thể chèn một giá trị cho trước vào mà không làm mất tính sắp xếp của phạm vi, nhưng phải đảm bảo giá trị được chèn vào sau tất cả các phần tử có giá trị bằng với nó (nếu có). Nói cách khác, nó trả về iterator trỏ đến phần tử đầu tiên trong phạm vi mà lớn hơn giá trị cho trước.

Tham số

first

• Forward Iterator trỏ đến phần tử đầu tiên trong phạm vi đã sắp xếp cần tìm kiếm.

last

• Forward Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi. Phạm vi là [first, last).

val

• Giá trị cần tìm vị trí chèn.

comp

• Một hàm hoặc đối tượng hàm (comparator) nhận hai đối số (một phần tử trong phạm vi và val) và trả về true nếu phần tử thứ nhất (trong phạm vi) được coi là nhỏ hơn val theo tiêu chí so sánh, false nếu ngược lại. (Phiên bản 2)

Giá trị trả về

• Forward Iterator trỏ đến phần tử đầu tiên trong phạm vi lớn hơn val. Nếu tất cả các phần tử trong phạm vi đều nhỏ hơn hoặc bằng val, iterator trả về sẽ là last.

Đặc điểm

1. Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
2. upper_bound() yêu cầu phạm vi đầu vào đã được sắp xếp theo thứ tự tương ứng (tăng dần hoặc theo comp).
3. upper_bound() trả về iterator trỏ đến phần tử đầu tiên lớn hơn val.
4. upper_bound() yêu cầu Forward Iterator, cho phép di chuyển một chiều về phía trước.
5. Trong C++11 trở lên, bạn có thể sử dụng biểu thức lambda cho hàm so sánh comp (phiên bản 2) để code ngắn gọn và dễ đọc hơn.
6. upper_bound() sử dụng thuật toán tìm kiếm nhị phân (binary search) để tìm kiếm vị trí, do đó, độ phức tạp thời gian là O(log n), trong đó n là số phần tử trong phạm vi.
7. Phạm vi đầu vào phải được sắp xếp theo thứ tự tăng dần (hoặc theo tiêu chí so sánh được cung cấp) trước khi gọi upper_bound(). Nếu phạm vi không được sắp xếp, kết quả sẽ không chính xác.
8. upper_bound() thường được sử dụng để:
   • Tìm vị trí thích hợp để chèn một phần tử vào một dãy đã sắp xếp mà vẫn giữ nguyên thứ tự, và đảm bảo vị trí chèn sau tất cả các phần tử có giá trị bằng với nó.
   • Tìm kiếm phần tử đầu tiên trong dãy đã sắp xếp có giá trị lớn hơn một giá trị cho trước.
   • Triển khai các cấu trúc dữ liệu và thuật toán dựa trên tìm kiếm nhị phân.

Phân biệt với lower_bound()

• lower_bound() trả về iterator trỏ đến phần tử đầu tiên không nhỏ hơn val.
• upper_bound() trả về iterator trỏ đến phần tử đầu tiên lớn hơn val.

Ví dụ

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm so sánh để tìm upper_bound trong dãy giảm dần
bool compareDescending(int a, int b) {
  return a > b; // Lưu ý: Đảo ngược logic so sánh cho dãy giảm dần
}

int main() {
  std::vector<int> numbers = {1, 3, 5, 5, 5, 7, 9};

  // Tìm vị trí chèn số 4 (sẽ chèn trước số 5 đầu tiên)
  auto it1 = std::upper_bound(numbers.begin(), numbers.end(), 4);
  std::cout << "Upper bound of 4: index " << (it1 - numbers.begin()) << ", value " << *it1 << std::endl;

  // Tìm vị trí chèn số 5 (sẽ chèn sau số 5 cuối cùng)
  auto it2 = std::upper_bound(numbers.begin(), numbers.end(), 5);
  std::cout << "Upper bound of 5: index " << (it2 - numbers.begin()) << ", value " << *it2 << std::endl;

  // Tìm vị trí chèn số 10 (sẽ chèn vào cuối)
  auto it3 = std::upper_bound(numbers.begin(), numbers.end(), 10);
  std::cout << "Upper bound of 10: index " << (it3 - numbers.begin()) << std::endl;
  if (it3 == numbers.end())
    std::cout << "Value: end()" << std::endl;

  std::vector<int> numbers2 = {9, 7, 5, 5, 5, 3, 1};

  // Tìm vị trí chèn số 6 trong dãy giảm dần
  auto it4 = std::upper_bound(numbers2.begin(), numbers2.end(), 6, compareDescending);
  std::cout << "Upper bound of 6 (descending): index " << (it4 - numbers2.begin()) << ", value " << *it4 << std::endl;

  return 0;
}

Các hàm liên quan

lower_bound	Tìm vị trí đầu tiên trong một phạm vi đã được sắp xếp mà có thể chèn một giá trị cho trước vào mà không làm mất tính sắp xếp của phạm vi
equal_range	Tìm phạm vi con trong một phạm vi đã được sắp xếp mà chứa tất cả các phần tử có giá trị tương đương với một giá trị cho trước
binary_search	Kiểm tra xem một giá trị cho trước có tồn tại trong một phạm vi đã được sắp xếp hay không, sử dụng thuật toán tìm kiếm nhị phân
max_element	Tìm phần tử có giá trị lớn nhất trong một phạm vi được chỉ định