= Two-sorted-array order statistic
{title2=$A_L\le B_R,\quad B_L\le A_R$}
To obtain the $k$-th smallest entry of two ascending <sorted arrays> of lengths $m,n$, choose prefix lengths $i,j$ with $i+j=k$. Search $\max(0,k-n)\le i\le\min(m,k)$ for the two boundary inequalities in the title, treating missing left boundaries as $-\infty$ and missing right boundaries as $+\infty$. Then all $k$ selected entries precede all unselected entries, so their largest boundary value is the answer. If $A_L>B_R$, decrease $i$; if $B_L>A_R$, increase $i$. These failures are monotone because one prefix grows as the other shrinks. <Binary search> thus takes $O(\log(\min(m,n)+1))$ comparisons when the shorter <array> supplies the searched prefix. Repeated values retain their multiplicities in the ranks.
Back to article page
