algorithm - 在 0-1 数组中找到所有 1“在左侧”的 1 的数量？

Question

一个数组由 N 个许多 1 和 0 组成，所有 1 都在任何 0 之前。在数组中查找没有 1。很明显，二分查找是 O(log N)。是否有算法在 O(log(number of 1's)) 时间内执行此操作？

Answer 1

你其实可以及时做到，1s的个数O(lg m)在哪里。m我不会给出整个算法，因为这看起来像家庭作业，但这里有一个提示：尝试“反转”二分搜索，以便扩大搜索区域而不是缩小搜索区域。

Answer 2

如果你只是迭代这个数组，你计算所有的 1，最后找到 0 你做了 N+1 步，所以在我看来它是 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));

    }

}