 Equal-range search

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.