java - 在数组中搜索不同的数字，当所有其他数字都相同时，可以使用分治法在 O(logn) 中完成吗

Question

假设我们有一个非常大的数组，我们需要找到数组中唯一不同的数字，数组中所有其他数字都相同，我们可以使用分治法在 O(log n) 中找到它吗，就像mergeSort一样，请提供实现。

Answer 1

这不可能以比 O(n) 更好的时间复杂度来完成，除非该数组是特殊的。根据您给出的约束，即使您应用分治法之类的算法，您也必须至少访问每个数组元素一次。

As dividing the array will be O(log n) and comparing 2 elements when array is reduced to size 2 will be O(1)

这是错误的。划分数组不是 O(log n)。像二进制搜索这样的东西在 O(log n) 中工作的原因是因为数组是排序的，这样你可以在每一步丢弃数组的另一半，即使不看它们有什么元素，从而将大小减半原始问题。

凭直觉，你可以这样想:即使你一直将数组分成两半，所形成的树的叶子节点也是n/2(考虑到你在叶子比较2个元素)。您将不得不进行 n/2 次比较，这导致 O(n) 的渐近复杂度。