Understanding Upper Bound and Lower Bound with Compare Function in C++

When working with sorted data collections in C++, efficiently finding elements or positions is crucial. The `upper_bound` and `lower_bound` functions are essential tools for operations involving sorted sequences such as arrays and vectors. Both functions are templated and reside in the ```<algorithm>``` library. At their core, these functions leverage binary search to deliver performance with logarithmic complexity. Let's explore how these functions operate, and how they can be customized using the compare function.

Overview of `upper_bound` and `lower_bound`

Both `upper_bound` and `lower_bound` are used to locate positions in sorted sequences. Here's a brief explanation of what each function does:

• `lower_bound(first, last, value, comp)`: Finds the first position where an element can be inserted without violating the order. Specifically, it returns an iterator to the first element in the range `[first, last)` that is not less than (`>=`) `value`.
• `upper_bound(first, last, value, comp)`: Finds the position just after the last occurrence of an element less than or equal to `value`. It returns an iterator to the first element in the range `[first, last)` that is greater than `value`.

Compare Function: Customizing the Behavior

The fourth parameter in `lower_bound` and `upper_bound` is a compare function, denoted as `comp`. This function allows you to override the default comparison behavior, making these functions incredibly versatile.

Signature of the Compare Function:

The compare function should fulfill the requirements of Strict Weak Ordering, which means it should compare two elements and return `true` if the first element is considered less than the second.

Example: Custom Compare for Descending Order

Suppose you have a list sorted in descending order, and you wish to find bounds using this order:

• Ensure sorting order: The compare function should align with the sorting order of the data collection to avoid undefined behavior.
• Consistent Criteria: Apply consistent criteria across all comparison-based operations to maintain logical integrity in the algorithm's use.
• Use Type Inference: Leverage C++'s type inference capabilities with auto when dealing with iterators.
• Finding Insert Positions: Utilize `lower_bound` when you aim to maintain order in a sorted container while inserting elements.
• Range Queries: Use both bounds to define range queries or subarray selections. For example, to perform binary search in a given range.