Understanding upper bound algorithm

The strategy from the earlier example could be used to create an algorithm. To explain this algorithm, we will use an array sorted in ascending order and find the upper bound of a target number.

Algorithm

The upper-bound algorithm is used to find the first position in a sorted array where a given target value can be exceeded. In other words, it returns the index of the first element that is strictly greater than the target value. This is useful for insertion, range queries, and counting elements greater than a value. The algorithm begins by initializing two indices that define the current search range in which the upper-bound may exist.

`low` is set to the first index of the array i.e `0`.

`high` is set to the last index of the array i.e `arr.size()` (one position past the last valid index).

These indices define a half-open search range [low, high), where low is inclusive and high is exclusive.

Why is high initialized to the array size?

Using high = arr.size() allows the algorithm to handle cases where the target value is greater than all elements in the array. In such cases, the upper bound is the end of the array, which represents the position immediately after the last occurrence of the target and is a valid insertion point to maintain the sorted order.

Initialize the low and high indices

The algorithm enters a loop that continues as long as low < high. This condition ensures that there is still at least one possible position where the upper bound could exist.