Given a sorted array with n integers, how to find the element that has no duplicates?

Question

I am given a sorted array with n integers. All of the elements repeat exactly twice, while there is one element without duplicate. I need to solve it as efficient as it is possible by divide-and-conquer algorithm. I have noticed that n needs to be odd to satisfy my condition. I thought about doing this: divide my array in two parts from the mid, if from [0, mid] or [mid, end] I have odd number of elements then my elements is in that half. So, recursively divide also that subarray and so on.

1. How to decide which part of the array to look at first?
2. Does this solution take O(logn)?
3. Is there other effective approach?

Answer 1

Assume elements start at index 0. N is odd.

Let mid be an even number close to the middle of the array. Compare a[mid-1] and a[mid]. There is an odd number of elements before mid-1 and an even number after mid.

If both numbers are equal then the unique one is in the left half < mid-1. If they are not equal then the unique one is in the right half starting at mid.

Answer 2

This is a classical problem when the array isn't sorted, which has a surprising, almost magical linear solution.

But here, with a sorted array, your idea is great.

The unique element will have an index $u$, and every element $a[i]$ will be exactly the same as either $a[i-1]$ or $a[i+1]$ (which are different). Assuming that arrays start at $0$, the shape of the (sorted) array is first a list of elements where $a[2i] = a[2i+1]$, then $a[u]$, then a list of elements where $a[2i-1] = a[2i]$.

So to decide where $u$ is, you can take a random position in the array, and just have to ask whether you're in the first part (where doubles start on even indexes) or the second part (where doubles start on odd indexes). This takes a constant number of operation by question, and each question reduces the size of the search array by $2$ (if you sample in the middle, of course).

So, to synthesize :

1. By looking in the middle, you ensure that the next part you have to look at will be as small as possible
2. This yields a $\log(n)$ algorithm
3. This approach is probably optimal, but the proof that there isn't something better to do must be quite hard, so I leave it to someone else ^^