#### Approach #1 Binary search [Accepted]

**Intuition**

It is a search problem request O(log n) time and O(1) space

**Algorithm**

Binary search is suitable method for search problem and its

time cost is O(log n)

The basic idea is that the single element is not the same as the left one and

the right one.

First, if the length of array is 1, the only element is the answer we are looking

for.If not, we do as follows.First We find the middle one of array,and assume if it

is single element or not.If it is not the single element, there are four possibilities.

Shown as follows:

Divide parts is odd and right one is different:[1 1 2 2 3 3 5] The middle element

is 2, it divides the array into two parts,[1 1 2] and [3 3 5](contain 3(odd) elements)

right of middle element is 3 which is not equal to 2. The answer is in [3 3 5].

Divide parts is odd and left one is different:[1 1 2 3 3 5 5],parts are [1 1 2] and

[3 5 5],the answer is [1 1 2]

Divide parts is even and right one is different:[1 2 2 3 3 5 5 6 6],parts are [1 2 2 3]

and [5 5 6 6],answer is in [1 2 2 3] which contain the same number 3 as the middle one.In this

situation we just need to put [1 2 2] into recursive function

Divide parts is even and left one is different:[1 1 2 2 3 3 5 5 6],parts are [1 1 2 2]

and [3 5 5 6],then we put [5 5 6] into recursive function

**Python**

```
class Solution(object):
def singleNonDuplicate(self, nums):
if(len(nums)==1):
return nums[0]
mid_place = len(nums)/2
mid = nums[mid_place]
if (mid!=nums[mid_place-1] and mid!=nums[mid_place+1]):
return mid
if(mid_place%2==0):
if (mid!=nums[mid_place-1]):
return self.singleNonDuplicate(nums[mid_place+2:])
return self.singleNonDuplicate(nums[:mid_place-1])
if (mid!=nums[mid_place-1]):
return self.singleNonDuplicate(nums[:mid_place])
return self.singleNonDuplicate(nums[mid_place+1:])
```

**Complexity Analysis**

- Time complexity : O(n).
- Space complexity : O(1).