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. 位運(yùn)算

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

2. 二分法，觀察哪邊是偶數(shù)，切分開來不相等：

    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
            '''如果一半正好是奇數(shù)，自減1這一半就是偶數(shù)，如果相等，那么這邊偶數(shù)的那一邊是不會出現(xiàn)這個(gè)單數(shù)，如果不相等，那就是在這一側(cè)；如果一半是奇數(shù)，如果不相等，那另一邊都是偶數(shù)則不會有這個(gè)單數(shù)，一定在自己這個(gè)奇數(shù)個(gè)的這邊，如果相等，那就在另一邊，因?yàn)橐粋€(gè)數(shù)不可能跟兩邊都相等'''
        return nums[start]