Lessons from Search Insert (Summary)

$1.$ Binary search works on any monotonic property (here: sorted order), not just exact matches.

$2.$ The $left$ pointer after binary search points to the first position where the condition holds.

$3.$ Every halving step reduces the problem by a factor of $2$, giving $O(\log n)$ time regardless of whether you find an exact match.