= Lower-bound search
{title2=$p=\min(\{i:a(i)\geq x\}\cup\{N\})$}
For a nondecreasing <sorted array> $a[0..N)$ and target $x$, find the unique position $p\in[0,N]$ such that every earlier value is below $x$ and every later value is at least $x$. Equivalently, $p=\min(\{i\in[0,N):a(i)\geq x\}\cup\{N\})$. Uniqueness follows because, if $p<q$ both satisfied the partition, $a(p)$ would have to be both at least $x$ and below $x$. A half-open search interval maintains an excluded prefix of smaller values and an excluded suffix of greater-or-equal values. Allowing the sentinel $N$ handles an empty array or a target beyond its last entry.
Back to article page
