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
两种方法：
- 位运算
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
for i in nums:
res ^= i
return res
- 二分法，观察哪边是偶数，切分开来不相等：
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]
