Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

share|improve this question
4  
To be exact: If you have an array of length n, filled with numbers starting at 0 and incrementing by 1 (besides one duplicate) then the largest element is n-2 (as can be seen in your example). –  Nobody May 27 at 13:30
6  
Just to nitpick, there's no reason to set dup to 0. It will be set before it is returned (and it is never read before then). Heck, you could get rid of dup entirely and just return where you set it - if you aren't dead set on using the Single Return Path. –  Tory May 27 at 14:48
2  
I have proposed an edit to fix the error in your code that codesparkle mentioned. But why is it there? Did you not copy paste working code? Or did you not test your code? Both would be against the site's rules. –  Nobody May 27 at 14:50
3  
Actually, I have a question: what are left and right supposed to be set to when the function is initially called? –  Tory May 27 at 14:57
2  
Your example array has 11 elements, but n is 9. Am I missing something? –  Alex Reynolds May 27 at 23:03

7 Answers 7

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);
share|improve this answer
3  
+1 for overflow –  Silviu Burcea May 28 at 8:59
    
What about checked(left + right) / 2? That way, the code stays readable, but is now protected from the unlikely case of overflow (by an exception). –  svick May 28 at 19:35
    
@svick No, don't check the addition. There is no reason for the mean of two ints to not fit within an int. –  200_success May 28 at 20:27

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.

share|improve this answer
5  
I'd personally put a space between if and the parenthesis. You don't usually put non alphanumeric characters inside a word, and you usually do use a space to separate words from other stuff. –  Bakuriu May 27 at 17:51

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);
share|improve this answer

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.

share|improve this answer

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;
    }
share|improve this answer
    
It is good to have some test cases but I would put them at the end of the answer (I scanned the question very fast and mistook the tests for a hardcoded solution to the OP's problem). –  Nobody Jun 1 at 15:56

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);
share|improve this answer

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;
}
share|improve this answer
    
Actually \$O(\frac{n}{3}+2)\$ is the same as \$O(n)\$ complexity wise (still it might be faster if measured but that is not what the \$O\$ notation is for). –  Nobody Jun 1 at 15:53
    
As written, this algorithm will fail anytime arr.Length % 3 == 0 (e.g., arr.Length == 3, arr.Length == 6, arr.Length == 9, etc.). –  László Koller Jun 16 at 17:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.