sorting - ソートされた無限バイナリ配列で最初に出現する 1

Question

有限サイズの配列の場合、二分探索を使用して O(log(n)) 時間で解を得ることができます。

インデックスを一定時間ルックアップする無限配列がある場合、配列がソートされていることがわかっている場合、1 の最初の発生をどのくらいの速さで見つけることができますか?

Answer 1

上記の質問は何ですか？無限配列に対する操作は何ですか? O(1) ルックアップ? おそらく最善の方法は、いくつかの n に対してインデックス 2^n の 1 が最初に出現するまで繰り返し検索し、次にバイナリ検索を実行することです。次に、 O(log(n)) でそれを見つけることが保証されます。ここで、n は最初のインデックスの位置です。

編集：追伸。配列が実際に無限であり、ゼロしか含まれていない場合、これは終了するとは限りません。