540.Single Element in a Sorted Array

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

两种方法：

1. 位运算

    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for i in nums:
            res ^= i
        return res

2. 二分法，观察哪边是偶数，切分开来不相等：

    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        start = 0
        end = len(nums)-1
        while(start<end):
            mid = (start+end)/2
            '''L=[3,3,7,7,|10,11,11]；而[1,1,2,2,3,|4,4,8,8]'''
            if mid%2 == 1:
                mid -= 1
            if nums[mid] == nums[mid+1]:
                start = mid+2
            else:
                end = mid
            '''如果一半正好是奇数，自减1这一半就是偶数，如果相等，那么这边偶数的那一边是不会出现这个单数，如果不相等，那就是在这一侧；如果一半是奇数，如果不相等，那另一边都是偶数则不会有这个单数，一定在自己这个奇数个的这边，如果相等，那就在另一边，因为一个数不可能跟两边都相等'''
        return nums[start]