Find the duplicate in a sorted array In less-than O(n)
Don't use (left + right) / 2 in a binary search, as (left + right) is vulnerable to overflow.  Java's binary search implementation had such a bug for some time.

Instead, do

int middle = left + (right - left) / 2;


Alternatively, you could do

int middle = (int)(unchecked((uint)left + (uint)right) &gt;&gt; 1);