假设我有一个看起来像的数组
[False, False, ..., False, True, True, True, ..., True, False, False, ...]
也就是说,一个False的块,后跟一个True块,然后是另一个False块.这些块中的任何一个都可以是零.
是否有一个次线性算法来查找第一个True的索引(如果存在)？len(array)如果不存在True,则此算法可以返回.
我知道如果没有第二个False块,这可以在O(lg n)时间内完成(并且基本上只是二进制搜索).但我真的不知道如何在线搜索这个案例,而且我无法找到任何说这种算法存在的东西,或者说没有可能.