= Equal-range search
{title2=$[\operatorname{lower\_bound}(x),\operatorname{upper\_bound}(x))$}
Find both the <lower-bound search> boundary $i$ and the <upper-bound search> boundary $j$ of a key $x$ in a <sorted array>. Every entry in $[i,j)$ is at least and at most $x$, so all are equal to $x$. Values immediately outside this interval, when present, are strictly smaller or strictly larger; the interval is consequently maximal. An absent key gives $i=j$ at its insertion position. Two <binary searches> give total <time complexity> $O(\log(N+1))$ under constant-cost comparison and indexed access.
Back to article page
