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]&lt;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) &gt;&gt; 1);