in short, it is a binary search

think this without the single element

since now it is even number length, middle index would always be the element of the pair.

Now we have a single element been add between these pair

so now if we get the middle, if it is not the end of the pair ,then the single element been added at the front of the middle. otherwise it been add to the after the middle.

```
class Solution(object):
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
i = 0
j = len(nums)-1
while 1:
if nums[i] != nums[i+1]:
return nums[i]
if nums[j] != nums[j-1]:
return nums[j]
mid = (i + j)/2
if nums[mid] == nums[mid+1]:
mid += 1
if mid % 2 == 0:
j = mid
else:
i = mid + 1
```