ORIGINAL TECHNICAL PRACTICE
Find a boundary with binary search
Explain a search that returns the first position whose sorted value is at least a target, including an empty array and a target greater than every value.
Written for independent practice. The model answer presents one approach; clarify constraints and explain alternatives.
A REASONED APPROACH
Model answer.
Search a half-open interval [lo,hi), initially [0,n). Keep the first feasible position inside that interval or at its right boundary; the answer may legitimately be n.
Work through it
- Define the predicate values[i] >= target and confirm it is monotonic because the input is sorted.
- Compute a midpoint without moving outside the interval. If the predicate is true, set hi to mid; otherwise set lo to mid+1.
- Stop when lo equals hi and return lo. Walk through duplicate values, an empty array, and an all-smaller array to establish the boundary behavior.
Tradeoffs to discuss
- Time is O(log n) comparisons and space O(1). Insertions into an array can still require O(n) movement even when the insertion position is found quickly.
Common pitfalls
- Mixing closed and half-open interval rules commonly skips the final candidate or creates an infinite loop. Unsorted input invalidates the predicate.