# 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】

【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