题目
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
示例
示例1
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例2
输入: [3,3,7,7,10,11,11]
输出: 10
题目分析
此题如果不考虑附加要求，十分简单，遍历一次即可。时间复杂度O(n)，空间复杂度O(1)。
考虑附加要求。由于题目数组除了单一元素以外的其他元素都会出现两次，因此数组元素个数必然是奇数。
由于题目要求的复杂度是O(log n)，所以考虑使用二分法来解决。利用双指针划分数组：
int left = 0;
int right = numsSize - 1;
mid = (left + right + 1) / 2;
找到中间索引后，检查中间索引的两侧元素与中间元素是否相等：
- 如果
nums[mid] == nums[mid - 1]，检验中间元素两侧的元素个数。 - 如果
nums[mid] == nums[mid + 1]，检验中间元素两侧的元素个数。 - 如果都不相等，那么说明中间元素就是那个不重复的元素。
解释一下检验中间元素两侧的元素个数，以示例1作为样本。
初始数组：
| 1 | 1 | 2 | 3 | 3 | 4 | 4 | 8 | 8 |
|---|
中间元素：
| 1 | 1 | 2 | 3 | 4 | 4 | 8 | 8 |
|---|
将中间元素与其前一位对比，发现相等，现在的数组：
| 1 | 1 | 2 | 4 | 4 | 8 | 8 |
|---|
左侧元素个数是3个，右侧元素是4个。
由于题目的数组只有一个元素是单独的，而其他元素都是有且只有2个，那么在原数组基础上删掉两次相同的元素后，剩下的元素依然是这样2m+n的形式搭配。
因此，在本题中的子数组如果个数为偶数，那么单一元素一定不在这个子数组中，将之抛弃即可。
if (nums[mid] == nums[mid - 1]){
if ((left + mid - 1) % 2 == 0){
left = mid + 1;
}else {
right = mid - 2;
}
}else if (nums[mid] == nums[mid + 1]){
if ((left + mid) % 2 == 0){
left = mid + 2;
}else {
right = mid - 1;
}
}else return nums[mid];
题目解答
int singleNonDuplicate(int* nums, int numsSize){
int left = 0;
int right = numsSize - 1;
while (left < right){
int mid = (left + right) / 2;
if (nums[mid] == nums[mid - 1]){
if ((left + mid - 1) % 2 == 0) {
left = mid + 1;
}else {
right = mid - 2;
}
}else if (nums[mid] == nums[mid + 1]){
if ((mid + left) % 2 == 0){
left = mid + 2;
}else {
right = mid - 1;
}
}else {
return nums[mid];
}
}
return nums[right];
}
