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

• 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 '14 at 13:30
• 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 '14 at 14:48
• 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 '14 at 14:50
• Actually, I have a question: what are left and right supposed to be set to when the function is initially called? – Tory May 27 '14 at 14:57
• Your example array has 11 elements, but n is 9. Am I missing something? – Alex Reynolds May 27 '14 at 23:03

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.

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


Alternatively, you could do

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

• 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 '14 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 '14 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.

• 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.

• 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 '14 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);


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.

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 == input ? 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;
}

• 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 '14 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);


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

• 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 '14 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 '14 at 17:18