algorithm - 为以下内容提出 O(logm) 算法

Question

我需要为以下内容提出一个算法：让我们假设我们有一个由零和一组成的数组。数组从数组的开头到索引 m 用 0 填充，所有剩余索引用 1 填充。我需要在 O(logm) 时间内找到这个索引 m。这是我的想法：我认为这就像二进制搜索，首先我查看数组的中间元素，如果它为零，那么我会忘记数组的左侧部分并对右侧部分执行相同的操作，并且继续这样，直到我遇到一个。如果中间元素是一个，那么我会忘记右边的部分并对数组的左边部分做同样的事情。这是一个正确的 O(logm) 解决方案吗？谢谢

Answer 1

它不是“像”二分查找——它是二分查找。不幸的是，它是O(logN)，不是O(logM)。

要在 中找到边界线O(logM)，请从另一端开始：尝试位置{1, 2, 4, 8, 16, ... 2^i}等，直到找到1。2^i然后对和之间的区间进行二分搜索2^(i+1)，其中2^i+1是您发现 a 的第一个位置1。

找到第一个1take O(logM)，因为每次迭代时索引都会加倍。之后，二分查找又取一个O(logM)，因为区间的长度2^i..2^(i+1)也小于M。