Find an indestructible element in a sorted array

Question

Source: Microsoft Interview Question

Given a sorted array in which each element is present twice, except for one that is present once, we need to find this element.

Now, the standard O (n) solution is to make an XOR of the list, which will return a non-propagating element (since all duplicated elements will be canceled.)

Is it possible to solve it faster if we know that the array is sorted?

Answer 1

Yes, you can use sorting to reduce complexity to O(log n) by doing a binary search.

Since the array is sorted, before the missing element, each value occupies the spots 2*k and 2*k+1 in the array (subject to indexing based on 0).

So, you go to the middle of the array, say index h and check index h+1 if h is equal, or h-1 if h is odd. If the missing element arrives later, the values ​​in these positions are equal, if they are earlier, the values ​​are different. Repeat until a missing item is found.

Answer 2

Do a binary “search” (rather a workaround) in the array, check both neighborhoods, if both of them differ from the value in the middle, you have a solution. This is O(log n) .