搜索数组中的不同数字，当所有其他数字相同时，可以使用分治法在O（logn）中完成

Question

可以说我们有一个非常大的数组，并且我们需要找到唯一不同的数字数组中，所有其他数字在数组中都是相同的，我们可以使用divide和conquer在O（log n）中找到它，就像mergeSort一样，请提供一个实现。

Answer 1

除非该数组是特殊的，否则这不能以比O（n）更好的时间复杂度完成。有了你所给出的约束，即使你应用了一个算法，如分而治之，你必须至少访问一次数组元素。

作为分割阵列将是O（log n）的和进行比较2个元素时阵列被减少到2号将是O（1）

这被错误地放置。划分数组不是O（log n）。二进制搜索在O（log n）中起作用的原因是因为数组是按排序的，这样，即使不查看它们具有的元素，也可以在每一步中丢弃数组的另一半，从而将数组的大小减半原来的问题。直觉上，你可以这样认为：即使你继续把数组分成两半，所形成的树的叶子节点是n/2（考虑你比较叶子上的2个元素）。你将不得不做n/2比较，这导致O（n）的渐近复杂性。