列の中央値を求める問題は，二分探索がしばしば有効です．答えを二分探索し，以下の判定問題を解きます．

• 正整数 \(x\) が与えられる．\(A\) から異なる \(2\) 要素を選んで文字列として結合して得られる整数のうち，\(x\) 以下のものは \(N(N-1)/2\) 個未満か？

上の条件を満たす正整数 \(x\) のうち，最小のものが求める答えです．

以下，判定問題の解き方を述べます．正整数 \(a,b\) を文字列として結合して得られる整数を \(a * b\) と表します．\(A_i * A_j \leq x\) を満たす \(i,j\,(i \neq j)\) の個数を数えます．そのために，\(i\) を固定したとき，\(A_i * A_j \leq x\) を満たす \(j\) の個数を数えます．

まず，\(A_i > x\) ならば，そのような \(j\) は存在しません．

次に，\(A_i \leq x\) の場合を考えます．\(y < z\) ならば \(A_i * y < A_i * z\) が成り立つという単調性があります．そのため，\(A_i * y \leq x\) が成り立つ最大の \(y\) を求められれば，\(A_j \leq y\) を満たす \(j\) の個数が求めるものです（\(A_i \leq y\) の場合，\(i\) の寄与を取り除く必要があることに注意してください）．

\(y\) を求めましょう．これは，「\(A_i \times 10^k + y \leq x,\, y \leq 10^k-1\) となる \(k\) が存在するような最大の \(y\)」と言い換えることができます．まず，\(A_i \times 10^p \leq x\) を満たす最大の \(p\) を求めます．もし \(\lfloor x / 10^p \rfloor < A_i\) ならば，\(k = p\) とでき，任意の \(y \leq 10^p - 1\) について \(A_i \times 10^p + y < x\) が成り立つので， \(y=10^p - 1\) が最大です．次に，\(\lfloor x / 10^p \rfloor = A_i\) の場合を考えます．\(y\) として \(p\) 桁の整数を取れる条件は，\(x - A_i \times 10^p \geq 10^{p-1}\) です．このとき，\(k = p\) とでき，\(y=x - A_i \times 10^p\) が最大です．そうでない場合，\(k=p-1\) とすることで，\(y = 10^{p-1}-1\) と取れます．これは \(p-1\) 桁の整数のうち最大のものなので，明らかにこれが可能な最大の \(y\) です．

\(A_j \leq y\) を満たす \(j\) の個数は，あらかじめ \(A\) をソートしておくことで，二分探索を用いて \(O(\log N)\) 時間で求められます．あるいは，\(y\) が \(A_i\) に関して単調減少であることを利用して，尺取り法により \(O(N)\) 時間で求めることもできます．

尺取り法を用いた場合，全体の時間計算量は \(O(N (\log N + \log \max A))\) です．