在O（logn）运行时间中通过数组？

Question

是否可以通过布尔数组来查找O（logn）运行时间中的假值？数组的索引从0运行到n-1。

如果是这样，我们将如何在java中做到这一点？伪代码很好。

Answer 1

不需要。如果没有关于阵列的更多信息，这是不可能的。

您可以做的最好的是O(n)，它从左向右遍历数组并检查每个项目。

如果数组排序，则需要两次检查，两端都会有一个错误值，即O(1)。

由矛盾的一个常见的证明：

假设算法工作正确。然后，在检查少于所有元素之后，该算法产生正确的答案。现在假设算法只看到true s，它会得出答案x。现在只改变值的算法有而不是检查，我总是可以构造一个算法失败的测试用例。因此，该算法必须检查（未排序）布尔数组的所有元素以确定是否全部为真。

Answer 2

无论你做什么，你都必须检查所有的值，以确保没有错误的价值。线性时间，平均n/2次检查。

Answer 3

通常情况下，答案是“否”：除非您知道有关数组项目的顺序，否则不能通过数组搜索小于O(N)的单个值。

例如，如果数组排序，您可以在O(log N)中找到正确的位置。

对于具有所有false S，如果有的话，在开始boolean阵列被排序装置，以及所有true S，如果有的话，在结束。如果是这种情况，您可以使用二分查找找到对数时间的“分界点”。