Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Follow up: Your solution should run in O(log n) time and O(1) space.

Example 1:

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

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

分析：

一开始无从下手，虽然知道是二分法，但是不知道怎么用。

看了提示发现要找到独立数出现前后，奇数偶数位的变化。

【1，1，3，3】

独立数出现前，相同数字的index为：偶，奇，偶，奇

【1，1，2，3，3】

独立数出现之后，变为了 偶，奇，独，奇，偶。

所以根据这个变化在二分的时候判断独立数是在左边还是在右边。

Solution：

def singleNonDuplicate(self, nums):
 “””
 :type nums: List[int]
 :rtype: int
 “””
 if not nums: return None
 if len(nums) == 1:
   return nums[0]
 
 i, j = 0, len(nums)-1
 
 while i < j:
   mid = i + (j-i)/2
   if nums[mid] != nums[mid-1] and nums[mid]!=nums[mid+1]:
     return nums[mid]
   elif nums[mid] == nums[mid+1]:
     if mid % 2 == 0:
       i = mid + 2
     else:
       j = mid — 1 
   else:
     if mid % 2 == 0:
       j = mid — 2
     else:
       i = mid + 1
 
 return nums[j]

看到一个大神的解法：

def singleNonDuplicate(self, nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) / 2
        if nums[mid] == nums[mid ^ 1]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

挺有意思的：

odd xor 1 == odd — 1

even xor 1 == event + 1