= Upper-bound search
{title2=$p=\min(\{i:a(i)>x\}\cup\{N\})$}
For a <sorted array> $a[0..N)$, find the unique boundary $p\in[0,N]$ with $a[0..p)\leq x<a[p..N)$. A <binary search> maintains $0\leq l\leq r\leq N$, an excluded prefix $a[0..l)\leq x$, and an excluded suffix $x<a[r..N)$. At an interior midpoint $m$, replace $l$ by $m+1$ when $a(m)\leq 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.
Back to article page
