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

Question

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)\$?

Answer 1

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);

Answer 2

A binary search is a very nice solution to this problem and you implementation is quite simple and clean. The only issue I find with this code is your style.

Your function DuplicateBinaryFind could be named better. Currently the name feels backwards (IfNotNullCheck vs CheckIfNotNull) and it also suggests its going to find a duplicate binary value. A better name would be something like FindDuplicateInteger or FindDuplicateValue.

Also, your spacing is inconsistent:

• You have a blank line after dup = DuplicateBinaryFind(...) in the true block of your if-statement, but not in the false block. This blank space isn't needed.
• You have single spaces between the arguments (which is good) in the DuplicateBinaryFind call in the false block of you if-statement, but not in the true block.

• Not quite an inconsistency, but you do not have spaces around conditional operators (i.e >, ==) and select mathematical operators. There should be single spaces around these to help improve readability:

  if(left == right)        
  int middle = (left + right)/2
  if(arr[middle] < middle)
  

  The space around mathematical operations is basically left up to preference, but try and make the statement as readable as possible by separating different 'levels' of the operation with space.

Answer 3

There is something a bug in your algorithm. Consider the input [0, 1, 1, 2].

First round.

left = 0
right = 3
middle = 1
array[middle] = 1
middle == array[middle]

Second round

left = 2
right = 3
middle = 2
array[middle] = 1
array[middle] < middle

Third round

left = 2
right = 1
middle = 1
array[middle] = 1
middle == array[middle]

Forth round

left = 2
right = 1
...

Infinite recursion!

Edit

You can avoid the infinite recursion by considering the middle value in the first case:

dup = DuplicateBinaryFind(arr,left, middle);

Answer 4

I don't know how to use your method. I don't know what is "left" and "right" and... I don't need or want to know. You should hide your details. Create method int FindDuplicate(int[] array) and inside you call your implementation. Also it would be nice to know do you retrun value or index of duplicate. Also your dup variable is unnecessary and confusing.

Answer 5

Here is an algorithm that checks for a single duplicate in \$O(\log n)\$ time. It performs a binary search on the sorted sequence. The binary search is driven by comparing the array index with the array element at that index. If the two integers match, then no duplicate can exist with a lower array index. Of course, it is very sensitive to the assumptions you presented in your question.

Here are test cases to validate the scenario:

    [TestMethod]
    public void DuplicateCheck()
    {
        // Assumptions:
        // - The array is sorted in ascending order.
        // - The array is only populated with integers starting with 0 
        //   with no integer values skipped.
        // - There is only one duplicate.

        Assert.AreEqual(9, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9 }));

        Assert.AreEqual(-1, CheckForSingleDuplicateInSequence(new int[] { }));
        Assert.AreEqual(-1, CheckForSingleDuplicateInSequence(new int[] { 0 }));
        Assert.AreEqual(-1, CheckForSingleDuplicateInSequence(new int[] { 0, 1 }));
        Assert.AreEqual(1, CheckForSingleDuplicateInSequence(new int[] { 0, 0 }));
        Assert.AreEqual(-1, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 2 }));
        Assert.AreEqual(1, CheckForSingleDuplicateInSequence(new int[] { 0, 0, 1 }));
        Assert.AreEqual(2, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 1 }));
        Assert.AreEqual(-1, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 2, 3 }));
        Assert.AreEqual(1, CheckForSingleDuplicateInSequence(new int[] { 0, 0, 1, 2 }));
        Assert.AreEqual(2, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 1, 2 }));
        Assert.AreEqual(3, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 2, 2 }));
        Assert.AreEqual(-1, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 2, 3, 4, 5, 6, 7 }));
        Assert.AreEqual(3, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 2, 2, 3, 4, 5, 6 }));
        Assert.AreEqual(7, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 2, 3, 4, 5, 6, 6 }));
        Assert.AreEqual(-1, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 }));
        Assert.AreEqual(9, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 }));
        Assert.AreEqual(23, CheckForSingleDuplicateInSequence(new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 22, 23 }));
    }

Here is the function:

    private static int CheckForSingleDuplicateInSequence(int[] input)
    {
        if (input == null)
        {
            throw new System.ArgumentNullException("input");
        }

        if (input.Length < 2)
        {
            return -1;
        }
        else if (input.Length == 2)
        {
            return input[0] == input[1] ? 1 : -1;
        }

        int leftIndex = 0;
        int rightIndex = input.Length - 1;
        int midIndex = (int)(((uint)leftIndex + (uint)rightIndex) >> 1);

        do
        {
            if (input[midIndex] == midIndex)
            {
                // evaluate current location with its right neighbor
                if (input[midIndex] == input[midIndex + 1])
                {
                    return midIndex + 1;
                }

                // fork right
                leftIndex = midIndex;
            }
            else
            {
                // evaluate current location with its left neighbor
                if (input[midIndex] == input[midIndex - 1])
                {
                    return midIndex;
                }

                // fork left
                rightIndex = midIndex;
            }

            midIndex = (int)(((uint)leftIndex + (uint)rightIndex) >> 1);
        } while (leftIndex < midIndex && midIndex < rightIndex);

        return -1;
    }

Answer 6

You could write the statement as:

int middle = (left+right) / 2;
return (arr[middle] < middle) ? DuplicateBinaryFind(arr, left, middle - 1) : DuplicateBinaryFind(arr, middle + 1, right);

Answer 7

There's another bug in your code. Your method is hardcoded to expect the values to be consecutive. Use random sorted values with one duplicate and it breaks. Which means it's only good for a very narrow scenario.

Here's a method that I think is approximately \$O(\frac{n}{3} + 2)\$, which is not as good as \$O(\log n)\$ but better than \$O(n)\$:

public static int DuplicateFind(int[] arr)
{
    int i = 2;
    for(; i < arr.Length; i += 3)
    {
        if(arr[i] == arr[i - 1])
            return i - 1;
        if(arr[i] == arr[i + 1])
            return i;
        if(arr[i - 2] == arr[i - 1])
            return i - 2;
    }
    if(arr.Length + 1 % 3 == 0 && arr[i - 1] == arr[i - 2])
    {
        return i - 2;
    }
    //Error code if no duplicate found
    return -1;
}