sorting - 在已排序的无限二进制数组中第一次出现 1

Question

对于有限大小的数组，我们可以使用二进制搜索在 O(log(n)) 时间内得到解。

如果我们有一个具有恒定时间查找索引的无限数组，如果我们知道数组已排序，我们能以多快的速度找到第一次出现的 1？

Answer 1

上面的问题是什么？你对无限数组的操作是什么？O(1) 查找？也许最好的办法是查找第一次出现的索引 2^n 的 1 对于某些 n，然后进行二进制搜索。然后保证在 O(log(n)) 中找到它，其中 n 是第一个索引的位置。

编辑：附言。如果数组确实是无限的并且只包含零，则不能保证终止。