バイナリ配列内の「0」を備えた「1」セルを見つける

Question

ゼロを保持するサイズnの配列を考えると、のインデックスを見つける必要があります 1 持っているセル 0 彼の右（当時の次のセル）には、特定の配列に複数のペアがある可能性があり、そのいずれかが問題ありません。配列はソートされていませんが、最初の要素は 1 そして最後の要素はです 0.

検索は$ o（ log n）$ timeである必要があります。バイナリ検索のバリエーションが答えだと思いますが、方法はわかりません。

Answer 1

元の質問を見た後、追加の情報があるようです。最初の要素は1であり、最後の要素は0であることを知っています。これは重要です！

実際、バイナリ検索でそれを解決できます。最初に、最初の要素が1で最後の要素が0の場合、配列に$ 1,0 $のサブシーケンスが必要であることを観察します。

$ a [1、...、n] $で配列を示します。 $ a [n/2] = 1 $の場合、サブアレイ$ a [n/2、...、n] $に$ 1,0 $ $ -SUBシーケンスがあります。 $ a [n/2] = 0 $の場合、サブアレイ$ a [1、...、n/2] $に$ 1,0 $ $ -SUBシーケンスがあります。

したがって、$ o（ log n）$時間を要するバイナリ検索を使用できます。