Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
我需要为以下内容提出一个算法:让我们假设我们有一个由零和一组成的数组。数组从数组的开头到索引 m 用 0 填充,所有剩余索引用 1 填充。我需要在 O(logm) 时间内找到这个索引 m。这是我的想法:我认为这就像二进制搜索,首先我查看数组的中间元素,如果它为零,那么我会忘记数组的左侧部分并对右侧部分执行相同的操作,并且继续这样,直到我遇到一个。如果中间元素是一个,那么我会忘记右边的部分并对数组的左边部分做同样的事情。这是一个正确的 O(logm) 解决方案吗?谢谢
它不是“像”二分查找——它是二分查找。不幸的是,它是O(logN),不是O(logM)。
O(logN)
O(logM)
要在 中找到边界线O(logM),请从另一端开始:尝试位置{1, 2, 4, 8, 16, ... 2^i}等,直到找到1。2^i然后对和之间的区间进行二分搜索2^(i+1),其中2^i+1是您发现 a 的第一个位置1。
{1, 2, 4, 8, 16, ... 2^i}
1
2^i
2^(i+1)
2^i+1
找到第一个1take O(logM),因为每次迭代时索引都会加倍。之后,二分查找又取一个O(logM),因为区间的长度2^i..2^(i+1)也小于M。
2^i..2^(i+1)
M