 Upper-bound search

For a sorted array $a[\mathrm{0..}N)$, find the unique boundary $p\in [0,N]$ with $a[\mathrm{0..}p)\le x<a[p..N)$. A binary search maintains $0\le l\le r\le N$, an excluded prefix $a[\mathrm{0..}l)\le x$, and an excluded suffix $x<a[r..N)$. At an interior midpoint $m$, replace $l$ by $m+1$ when $a(m)\le x$, and otherwise replace $r$ by $m$. Sortedness preserves the loop invariant; the width $r-l$ is a decreasing loop variant. Termination at $l=r$ gives the boundary, including $p=0$ and $p=N$. The time complexity is $O(\log (N+1))$ with constant-cost comparisons and indexed access. Unlike searching for $x+1$, this formulation does not risk integer overflow at the largest representable key.