Why Binary Search Works

The tails array maintains the smallest ending element for each LIS length. $tails[k]$ = smallest last element of any LIS of length $k+1$. Key invariant: $tails$ is always sorted. Why? A longer LIS must end with a larger element than a shorter one ending at an earlier position.

When we see a new element $x$: if $x > tails[last]$, we can extend. Otherwise, find the first $tails[k] \geq x$ and replace it. Replacing keeps $tails$ optimal: we now have a smaller ending element for that length, enabling more extensions later.