BFE.devでのAI解答例 - JavaScript コーディング問題
136. 二つのソート済みの配列の中央値

初回の実装の時間コストはO(m+n)で、mとnはそれぞれ2つの配列の要素数です。空間コストはO(m+n)です。これは2つの配列を結合して、関数内で新しい配列を作成するためです。

より効率的な実装として、以下の方法が挙げられます。

1. 二分探索

片方の配列をループし、それぞれの要素に対してもう片方の配列で二分探索を行い、中央値を見つけます。この方法の時間コストはO(m log n)またはO(n log m)のいずれかです。

2. マージ

2つの配列をマージし、中央値を直接見つけます。この方法の時間コストはO(m+n)で、空間コストはO(1)になります。

実際の実装には、どちらの方法が最適かは入力データによって異なるため、実測の上で判断する必要があります。