一个数组由 N 个 1 和 0 组成，所有 1 都在任何 0 之前。在数组中查找 1 的个数。很明显，使用二分查找是 O(log N)。是否有一种算法可以在 O(log(1 的数量)) 时间内完成此操作？
最佳答案
您实际上可以在 O(lg m) 时间内完成，其中 m 是 1 的数量。我不会给出整个算法，因为这看起来像是家庭作业，但这里有一个提示:尝试“反转”二分搜索，以便扩大而不是缩小搜索区域。
关于algorithm - 在 0-1 数组中查找所有 1 为 “on the left” 的 1 的个数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15372070/