问题：

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.

Example 1:

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

Example 2:

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

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

解决：

① 难道不是跟Single Number一样的吗。。O(n)

class Solution { //2ms

    public int singleNonDuplicate(int[] nums) {         int xor = 0;         for (int n : nums){             xor ^= n;         }         return xor;     } }

② 用二分查找解决。O（lgn）

class Solution { //1ms

    public int singleNonDuplicate(int[] nums) {         int left = 0;         int right = nums.length - 1;         while(left < right){             int mid = (right - left) / 2 + left;             if (mid % 2 == 1) mid --;             if (nums[mid] != nums[mid + 1]){                 right = mid;             }else {                 left = mid + 2;             }         }         return nums[left];     } }