Understanding lower bound algorithm

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

Algorithm

The lower-bound algorithm finds the first position in a sorted array where a given target value can be inserted without violating the sorted order. In other words, it returns the index of the first element that is greater than or equal to the target value. The algorithm begins by initialising two indices that define the current search range in which the lower-bound may exist.

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

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

These indices define a half-open search range [low, high), where low is inclusive and high is exclusive (the position at index high is not part of the search range).

Why is high initialized to the array size?

Using high = arr.size() allows the algorithm to naturally handle cases where the target value is larger than all elements in the array. In such cases, the lower bound is the end of the array, which is a valid insertion position.

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 lower bound could exist.