[解決済み] 並べ替えられた2つの配列の和で、k番目に小さい要素を見つけるにはどうすればよいですか？

質問

これは宿題のようなもので、バイナリサーチはすでに紹介されています。

2つの配列が与えられたとき、それぞれ N と M の要素を昇順に並べたもので、一意である必要はありません。

を見つけるための時間効率のよいアルゴリズムは何か？ k を求める時間効率のよいアルゴリズムは何ですか？

が必要だそうです。 O(logN + logM) ここで N と M は配列の長さです。

配列の名前を a とし b . 当然ながら、すべての a[i] と b[i] ここで、i > k。

まず、比較してみましょう。 a[k/2] と b[k/2] . とする。 b[k/2] > a[k/2] . したがって、すべての b[i] ここで、i > k/2。

これで、すべての a[i] であり、i < k であり、すべての b[i] であり、i < k/2で答えを見つけることができます。

次のステップは何でしょうか？

どのように解決するのですか？

もう大丈夫です、続けてください。そして、インデックスには気をつけましょう...。

少し単純化するために、NとMを> kとすると、ここでの複雑さはO(log k)、つまりO(log N + log M)となる。

擬似コードです。

i = k/2
j = k - i
step = k/4
while step > 0
    if a[i-1] > b[j-1]
        i -= step
        j += step
    else
        i += step
        j -= step
    step /= 2

if a[i-1] > b[j-1]
    return a[i-1]
else
    return b[j-1]

デモのために、ループ不変量 i + j = k を使うことができますが、私はあなたの宿題をすべてやるつもりはありません :)