= Solution
Assume ascending <sorted arrays>; descending storage can be accessed in reverse index order without copying. Among $2n$ entries, the requested rank is \b[$k=n+1$ in ascending order], not $n$. Repeated values occupy repeated ranks.
Choose $i$ entries from the first <array> and $j=k-i$ from the second, using their prefixes. The feasible range is $\max(0,k-n)\le i\le\min(n,k)$. Write $A_L=A[i]$, $A_R=A[i+1]$, and similarly $B_L,B_R$ at $j$, with missing left endpoints replaced by $-\infty$ and missing right endpoints by $+\infty$. These are conceptual sentinels, not extra stored entries.
Use <binary search> over the feasible values of $i$:
* If $A_L>B_R$, there are too many entries from $A$ on the left; decrease the upper bound to $i-1$.
* If $B_L>A_R$, there are too few entries from $A$ on the left; increase the lower bound to $i+1$.
* Otherwise return \b[$\max(A_L,B_L)$].
For correctness, in the last case every left entry is no greater than every right entry, and exactly $k$ entries lie on the left. Their <maximum> is therefore the $k$-th smallest entry. The failed inequalities are monotone in the searched index: increasing $i$ raises the $A$ boundary and decreases the $B$ boundary, so it cannot repair $A_L>B_R$; the other case is symmetric. A partition of the first $k$ entries of a merged ordering supplies an admissible solution, including ties. Each step halves an interval with at most $n+1$ choices, giving \b[$O(\log(n+1))$ <running time> and $O(1)$ <auxiliary space>]. This is a <two-sorted-array order statistic> without constructing the merged <array>.
Back to article page
