difference between lower and upper bound

lower_bound and upper_bound are functions in C++'s Standard Template Library (STL) used with sorted containers like vectors and arrays. lower_bound returns an iterator pointing to the first element in the range [first, last) that is not less than a specified value. It performs a binary search and finds the position where the value can be inserted without disrupting the sorting order. If the value exists in the container, it returns an iterator to the first occurrence of that value.

On the other hand, upper_bound returns an iterator pointing to the first element in the range [first, last) that is greater than a specified value. Similar to lower_bound, it utilizes a binary search and locates the position where the specified value can be inserted without violating the sorted order. If the value exists in the container, it returns an iterator to the element just after the last occurrence of that value.

Here's a breakdown of both functions:

  • lower_bound:

    1. It performs a binary search on the sorted range [first, last) to find the position where the specified value can be inserted while maintaining the sorting order.
    2. Returns an iterator pointing to the first element that is not less than the specified value.
    3. If the value exists in the container, it returns an iterator to the first occurrence of that value.
    4. Complexity: O(log n), where n is the number of elements in the container.

  • upper_bound:

    1. Conducts a binary search on the sorted range [first, last) to find the position where the specified value can be inserted while preserving the sorted order.
    2. Returns an iterator pointing to the first element that is greater than the specified value.
    3. If the value exists in the container, it returns an iterator to the element just after the last occurrence of that value.
    4. Complexity: O(log n), where n is the number of elements in the container.

These functions are especially useful in scenarios where you need to efficiently find the insertion point for a value or locate the range of elements equal to a particular value within a sorted sequence.