*There is a sorted array, where every element appears in the array twice, except one, that appears once. The task is to find this element. As an example we may consider [1, 1, 2, 3, 3, 5, 5] and the element that we look for is 2. Can we achieve it in O(log n) and in place?*

Let’s consider what we know already about the problem.

(1) The information, that the array is sorted, is pretty useful, as it means** all the repeated elements are consecutive** (i.e 1,1 or 3,3). Moreover we know that **the element, that we are looking for, has to be located somewhere between those continuous 2-elements sequences** (i.e 1,1, **2**, 3, 3 is correct, but 1, **2**, 1, 3, 3 is not).

(2) All the elements appears twice, except one: it means that the **size of the array is an odd number**.

(3) If there is no extra element, it should contain only elements repeated twice and it should contain each of them. I mean in this case we would have [1, 1, 3, 3], [4, 4, 5, 5] so every occurrence of 1 and 3 appears in the left part. If an extra element is introduced to this part, we would have an inbalance of the amount of occurrences of the last element (it would overlow to the right part). It would be something like [1, 1, 2, 3], [3, 4, 4, 5, 5].

As we have just identified the properties, we can see **that the non repeating number is located in the odd-size part of the array**. **The binary search always divides the search space into two pieces. Dividing an odd size space, gives two subspaces – one of the even size, and the second one of the odd size**.

Unfortunately, dividing the array into two subarrays doesn’t give as any information which half is the odd size, and which is the even size. But we can **divide the array arbitrary, so that the first half is always even size**. Then **comparing the last element L of the left subarray to the first element R of the right subarray, is sufficient to establish, in which half the extra element is located.** If L != R then we need to check the second half of the array, otherwise the left one.

On the base of the previous paragraph we can develop an algorithm described in the pseudocode below.

int findOneElement(int array[], int size)
{
if(size == 1)
return array[0];
int medium = size/2;
// make the size even number
medium = medium % 2 == 0 ? medium : medium + 1;
if(array == array)
{
// look in the left subarray
return findOneElement(array, medium - 1);
}
else
{
// look in the right subarray
return findOneElement(array + medium + 1, size - (medium + 1));
}
}

The complexity is obviously O(log n) as we are using binary search. Moreover we don’t use any extra memory, so we get O(1). All the requirements are met.

Best Regards

Joe Kidd

### Like this:

Like Loading...