This lower-bound trace assumes an array sorted in ascending order and searches for the first index whose value is at least target. The half-open interval [lo, hi) contains every candidate position. The invariant is that the answer remains inside this interval.
1. Establish the candidate range
Set lo = 0 and hi = n. For an empty array, the range is already empty and the answer is 0. Using a half-open interval makes the end boundary represent the position after the last element.
2. Probe the middle
While lo < hi, compute mid = lo + (hi - lo) / 2 and load array[mid]. This form avoids overflowing lo + hi in languages with bounded signed integers. The load may hit cache or incur a miss; the algorithmic comparison count does not reveal that latency.
3. Keep the side that can contain the answer
If array[mid] < target, every position through mid is too small, so set lo = mid + 1. Otherwise mid may itself be the first acceptable index, so set hi = mid. Each update strictly shrinks the candidate interval.
4. Return the boundary
When lo == hi, that position is the first element not less than the target, or n if no such element exists. Duplicates are handled correctly because equal values move the upper boundary left. The sorted-input precondition is essential; without it, discarding a half is not justified.