Binary search halves the search space each iteration — O(log n) on a sorted collection. The half-open invariant [low, high) makes every variant consistent: low is inclusive, high is exclusive. Lower-bound finds the first position ≥ target; upper-bound finds the first position > target. Binary search on the answer solves monotonic problems by searching over a solution space rather than an array.
Each stage in order — click any step to read what it does.
The single template that solves lower-bound, upper-bound, and all binary search variants.
The trade-offs worth knowing before you build this.
For large indices, low+high overflows int. Always use low + (high-low)/2.
The half-open [low,high) invariant with "if pred: high=mid; else: low=mid+1" works for every binary search variant. Memorise one pattern.
"Find minimum speed to deliver packages in D days" → binary search over speed values with a canDeliver(speed) predicate.
Sign in to share your feedback and join the discussion.
