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