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.
- How to decide which part of the array to look at first?
- Does this solution take O(logn)?
- Is there other effective approach?