在falses海中寻找真实的岛屿

Question

假设我有一个看起来像的数组

[False, False, ..., False, True, True, True, ..., True, False, False, ...]

也就是说,一个False的块,后跟一个True块,然后是另一个False块.这些块中的任何一个都可以是零.

是否有一个次线性算法来查找第一个True的索引(如果存在)？len(array)如果不存在True,则此算法可以返回.

我知道如果没有第二个False块,这可以在O(lg n)时间内完成(并且基本上只是二进制搜索).但我真的不知道如何在线搜索这个案例,而且我无法找到任何说这种算法存在的东西,或者说没有可能.

Answer 1

不,最糟糕的情况必须是O(n) - 无论你选择哪种顺序来检查数组,都可能有一个真正的内部,它最终可能会在你看到的最后一个索引中.

编辑:实际上,即使是最简单的最坏情况也是根本没有真实的情况.如果不查看数组的每个元素,都无法确定.