### 题目

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.

### 标准Set解法，$O(n)$

#### 代码

public class Solution {
public int singleNonDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n : nums) {
}
return set.iterator().next();
}
}


### 用XOR位操作，$O(n)$

#### 代码

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


### 利用排过序这个特性，$O(n)$

#### 代码

public class Solution {
public int singleNonDuplicate(int[] nums) {
if (nums.length == 0) { return 0; }
int cur = 1;
while (cur < nums.length) {
if (nums[cur-1] != nums[cur]) { return nums[cur-1]; }
cur += 2;
}
return nums[cur-1];
}
}


### 二分查找，$O(\log_{}{n})$

#### 代码

public class Solution {
public int singleNonDuplicate(int[] nums) {
int lo = 0, hi = nums.length-1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int even = (mid % 2 == 0)? nums[mid] : nums[mid-1];
int followingOdd = (mid % 2 == 0)? nums[mid+1] : nums[mid];
if (even == followingOdd) {
lo = mid + 1;
} else {
hi = (mid / 2) * 2;
}
}
return nums[lo];
}
}