2つのソート済み配列の中央値

2つのソート済み配列の中央値

2つのソート済みリストを結合したときの中央値を求めてください。

このチャレンジで学べること

両方のリストは昇順にソートされています。2つのリストのすべての要素を合わせたときの中央値を求めてください。要素数が偶数の場合は中央2つの値の平均を返します。O(log(m + n))の分割探索も可能ですが、制約内で正しい方法であればどの実装でも構いません。

median_of_two(first, second) を実装してください。

first: ソート済みリスト。 second: ソート済みリスト。

中央値を返してください。

0 ≤ 長さ ≤ 100,000；2つのリストを合わせた長さは1以上

例 1

入力：
first = [1, 3]
second = [2]

期待される出力：
expected = 2.0

入力：
std::vector<long long> first = {1, 3};
std::vector<long long> second = {2};

期待される出力：
double expected = 2.0;

入力：
long[] first = new long[] {1, 3};
long[] second = new long[] {2};

期待される出力：
double expected = 2.0;

結合後: [1, 2, 3]; 中央値は2です。

例 2

入力：
first = [1, 2]
second = [3, 4]

期待される出力：
expected = 2.5

入力：
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};

期待される出力：
double expected = 2.5;

入力：
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};

期待される出力：
double expected = 2.5;

結合後: [1, 2, 3, 4]; (2 + 3) / 2 = 2.5 です。

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

全体の順序は重要だが、中央の分割を直接見つけられるなら全部マージする必要はない。

ヒント 2

左半分が下位の中央要素をちょうど含み、かつ左側の値がすべて右側以下になるような分割を探す。

ヒント 3

空配列や要素数が奇数・偶数の場合を丁寧に扱おう。中央値は中央の1つの値になることも2つの平均になることもある。

目安の計算量

時間 O(log(min(m, n)))、追加メモリ O(1)

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。