algorithm - 「左側」がすべて 1 の 0-1 配列の 1 の数を見つけますか?

Question

配列は N 個の 1 と 0 で構成され、すべての 1 はすべての 0 の前にあります。配列内の 1 を見つけます。二分探索では O(log N) であることは明らかです。O(log(1の数))時間でこれを行うアルゴリズムはありますか?

Answer 1

実際にはO(lg m)時間内に実行できmます。 は 1 の数です。これは宿題のように見えるので、アルゴリズム全体を説明することはしませんが、ここにヒントがあります。バイナリ検索を「逆」にして、検索領域を縮小するのではなく拡大するようにしてください。

Answer 2

この配列を反復処理すると、すべての 1 がカウントされ、最終的に N+1 ステップを作成した 0 が見つかるため、私の意見では O(n+1) アルゴリズムです。

Answer 3

class OneZero
{

    public static int binary_search (byte[] array, int start, int end, int value)
    {

        if (end <= start) return -1;

        if (Math.floor((start+end)/2) == value) return Math.floor((start+end)/2);

        return binary_search (array, start, Math.floor((start+end)/2)-1, value);

    }

    public static int nbOfOnes (byte[] array, int value)
    {

        return (binary_search(array, 0, array.length,value)+1);

    }

    public static void main ()
    {

        byte[] arr = { 1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0 };

        System.out.println(" number of 1s is: "+nbOfOnes(arr,1));

    }

}