※ 引述《Rushia (みけねこ的鼻屎)》之铭言：
: 540. Single Element in a Sorted Array
: 给你一个已排序整数阵列，里面的所有数字都有恰好两个，只有一个数字只有一个，
: 找出这个数字是什么，限制时间复杂度：O(logn)且空间复杂度：O(1)。
: Example :
: Input: nums = [1,1,2,3,3,4,4,8,8]
: Output: 2
: Input: nums = [3,3,7,7,10,11,11]
: Output: 10
解题思路:
一样用 binary search 维护左右边界，
左边界 l: 保证不是答案的最大值，初始为 -1，
右边界 r: 可能是答案的最小值，初始为 size - 1。
由于 l 左边保证不是答案，所以一定是偶数个数字，
戳到 mid 如果是奇数index (含自己左边有偶数个数字)，只要跟左边相邻数字检查，
戳到 mid 如果是偶数index (不含自己左边有偶数个数字)，只要跟右边相邻数字检查，
等到边界 l + 1 == r 的时候 nums[r] 就是答案。
C++ code:
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int l = -1, r = nums.size() - 1;
while(l + 1 < r){
int mid = (l + r) / 2;
if(mid & 1){
if(nums[mid] == nums[mid - 1]) l = mid;
else r = mid;
}
else{
if(nums[mid] == nums[mid + 1]) l = mid + 1;
else r = mid;
}
}
return nums[r];
}
};