次のアルゴリズムを提案する必要があります。0と1で構成される配列があると仮定します。配列は、配列の先頭からインデックスmまでゼロで埋められ、残りのすべてのインデックスは1で埋められます。このインデックスmをO（logm）時間で見つける必要があります。これが私が考えたものです：これは二分探索のようなものだと思います。最初に配列の中央の要素を見て、それがゼロの場合、配列の左側の部分を忘れて右側の部分についても同じことを行います。私が1つに遭遇するまでこのように続けてください。真ん中の要素が1つである場合、右側の部分を忘れて、配列の左側の部分についても同じことを行います。これは正しいO（logm）ソリューションですか？ありがとう
1 に答える
4
それは二分探索の「ような」ものではなく、二分探索です。残念ながら、そうではありません。O(logN)O(logM)
の境界線を見つけるにはO(logM)、もう一方の端から開始します。位置{1, 2, 4, 8, 16, ... 2^i}などを試して、をヒットするまで続けます1。2^i次に、との間の間隔で二分探索を実行します。2^(i+1)ここ2^i+1で、はを発見した最初の位置です1。
インデックスは反復ごとに2倍になるため、最初の検索には1がかかります。O(logM)その後O(logM)、区間の長さ2^i..2^(i+1)もより短いため、二分探索はさらに時間がかかりMます。
于 2013-03-10T13:17:42.393 に答える