arrays - O（log n）時間で配列内の重複要素を見つける

Question

同様の質問が何度も出される可能性があることは承知していますが、それらとは異なります。

値1 to N-1を持つ並べ替えられていない整数配列に 1 つの重複要素があるとします (Nは配列のサイズであり、最大値はN-1重複要素によるものです)。重複する要素を見つける最良の方法は何ですか? できればO(log n).`

私はO(n)解決策を知っていますが、この問題をO(log n)時間内に解決する方法はありますか?

O(n) ソリューション:

1) Find sum of first N-1 natural numbers using N(N-1)/2, lets say it SUM1
2) Find sum of all the elements of the arrays, let say it SUM2

Duplicate = SUM2 - SUM1

Answer 1

サブリニアに行うことはできません。配列はソートされていないため、最悪の場合はすべての要素を読み取る必要があります。

この直感は非常に一般的であり、ソートされていない配列を扱う多くのアルゴリズムに当てはまります。

もちろん、並べ替えられた配列を使用した質問には、同じ直感は当てはまりません。