Find the duplicate in a sorted array In less-than O(n)

Assumptions:

• The array is sorted.

• There is only one duplicate.

• The array is only populated with numbers [0, n], where n is the length of the array.

Example array: [0,1,2,3,4,5,6,7,8,8,9]

Here is my implementation:

public static int DuplicateBinaryFind(int[] arr, int left, int right)
{
   int dup =0;

   if(left==right)
   {
      dup = left;
   }
   else
   {
        int middle = (left+right)/2;
        if(arr[middle]<middle)
        {
          dup = DuplicateBinaryFind(arr,left, middle-1);

        }
        else
        {
           dup = DuplicateBinaryFind(arr, middle+1, right);
        }
   }

   return dup;

}

Is this considered as good solution to the problem as it finds the duplicate in \$O(\log 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) >> 1);

StackExchange Code Review Q#51822, answer score: 16