search value in unsorted array in O(log n)

Question

My friend got a question in a test , the question was:

You get an unsorted array with integer values as pairs , and 1 value as single for example:

[1,1,5,5,2,2,4,4,7,12,12,8,8]

The output is: 7

Now I know binary search can do it with O(log n) but the array need to be sorted.

So how can it be done in O(log n) on this unsorted array ?

Answer 1

Let us consider the auxiliary array formed by taking every other number and assigning 0 if equal to the next and 1 otherwise.

[1,1,5,5,2,2,4,4,7,12,12,8,8]
[0,  0,  0,  0,  1,   1   ]

This auxiliary array is clearly sorted and the first 1 can be found by binary search.

Of course the array mustn't be constructed explicitly, as this would take O(N).

Answer 2

You can also do a binary search in an unsorted array if the value pairs are next to each other:

1. Split the array that must have 2n + 1 elements as follows: <n elements> <1 element> <n elements>:
2. Compare the middle element to the last element of the first part and to the first element of the second part:
   • if it is not equal to both, the single element have been found
   • otherwise, add the middle element to the part with the same element (if it is equal to the last element of the first part, append it to the first part, otherwise add it as the first element to the second part)
3. Repeat the steps with the part that has an odd number of elements

Answer 3

If suffices to notice that all pairs on the left of the singleton are on even/odd indexes and those on the right are on odd/even.

As the parity of the pair to which an arbitrary element belongs can be found in constant time, a dichotomic process to find the parity transition is indeed possible.

This only holds if the neighboring pairs are different or if the runs of equal pairs never exceed a length O(1). For instance with a single 7 among all pairs of 8's, only a linear search can do.