Hàm set::lower_bound() trong C++ STL

set::lower_bound(k) trả về iterator trỏ đến phần tử đầu tiên không nhỏ hơn k (tức ≥ k). Nếu tất cả phần tử < k, trả về end().

Đặc điểm

Độ phức tạp: O(log n) (tìm kiếm nhị phân trên tree).
Không sửa đổi container.
Có overload const và non-const.
Tương tự: upper_bound(k) – phần tử đầu tiên > k.

Ví dụ

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 4, 6, 7, 9, 10};

    auto it = s.lower_bound(4);
    cout << "lower_bound(4): " << (it != s.end() ? to_string(*it) : "end()") << endl; // 4

    it = s.lower_bound(5);
    cout << "lower_bound(5): " << (it != s.end() ? to_string(*it) : "end()") << endl; // 6

    it = s.lower_bound(30);
    cout << "lower_bound(30): " << (it != s.end() ? to_string(*it) : "end()") << endl; // end()

    // Ứng dụng: chèn có thứ tự, tìm khoảng
    // [lower_bound(a), upper_bound(b)) = các phần tử trong [a, b]
    auto first = s.lower_bound(3);
    auto last  = s.upper_bound(8);
    cout << "Elements in [3,8]: ";
    for (auto it = first; it != last; ++it) cout << *it << ' '; // 4 6 7
    cout << endl;

    return 0;
}

Kết quả

lower_bound(4): 4
lower_bound(5): 6
lower_bound(30): end()
Elements in [3,8]: 4 6 7

So sánh lower_bound vs upper_bound

Hàm	Trả về	Ví dụ set {1,4,6}
`lower_bound(4)`	≥ 4 → 4	4
`upper_bound(4)`	> 4 → 6	6
`lower_bound(5)`	≥ 5 → 6	6
`upper_bound(5)`	> 5 → 6	6
`equal_range(4)`	pair(lower, upper)	{4, 6}

Ứng dụng thực tế

Tìm khoảng [l, r]: [lower_bound(l), upper_bound(r)).
Chèn giữ thứ tự: s.insert(lower_bound(x), x) (hint cho insert – amortized O(1) nếu hint đúng).
Coordinate compression (discretization).
Order statistics (k-th smallest) – cần policy-based data structure (GNU PBDS).

Lưu ý

Luôn kiểm tra it != s.end() trước khi dereference.
std::lower_bound (algorithm) làm việc trên bất kỳ RandomAccessIterator (vector, array) – O(log n) nhưng cần random access.
set::lower_bound tối ưu cho tree (không cần random access).