题目：
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。请你找出并返回只出现一次的那个数。你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: nums = [3,3,7,7,10,11,11]
输出: 10
提示:
1 <= nums.length <= 1050 <= nums[i] <= 105
思路：
题目有两个已知条件：
1.数组是有序的。
2.除了一个数出现一次外，其余每个数都出现两次。
第二个条件意味着，数组的长度一定是奇数。
第一个条件意味着，出现两次的数，必然相邻，不可能出现 1,2,1 这样的顺序。
这也意味着，只出现一次的那个数，一定位于偶数下标上。
这启发我们去检查偶数下标 2k。
示例 1 的 nums=[1,1,2,3,3,4,4,8,8]：
如果 nums[2k] = nums[2k+1]，说明只出现一次的数的下标 >2k。
如果 nums[2k] != nums[2k+1]，说明只出现一次的数的下标 ≤2k。
也就是说，随着 k 的变大，不等式 nums[2k] != nums[2k+1] 越可能满足，有单调性，可以二分。
0 <= k <= n/2 - 1
代码：
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left = 0, right = nums.size() / 2;
while (left <= right) {
int mid = left + (right - left) / 2;
int leftIdx = mid * 2, rightIdx = leftIdx + 1;
if (rightIdx >= nums.size() || nums[leftIdx] != nums[rightIdx]) right = mid - 1;
else left = mid + 1;
}
return nums[left * 2];
}
};