未定義の配列をlogrithmic timeで検索する

Question

私は現在、アルゴリズムの紹介のための試験のために勉強しています。私は本当に解決できないという質問に出くわしました。問題はこれです。あなたはn個の整数の配列を持っています。最初のm個の要素は偶数であり、残りの要素は奇数である。あなたは、mの値を見つけ出す（最後の偶数のインデックスを見つける）アルゴリズムを書く必要があり、時間複雑さはO（log m）です。

私はバイナリ検索に似たようなことを考え、単に奇数の場合は左に移動し、偶数でも次のものが奇妙なインデックスを見つけるまでは右に移動しますが、このことはO（log n） O（log m）ではない。

Answer 1

インデックス1から開始し、奇妙なエントリが見つかるまで、インデックスを倍増し続けます。これにより、時間O（log m）のmの上限が得られます。次に、バイナリ検索を実行します。