1、题目描述：
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 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
2、代码：
错误的代码
class Solution
{
public:
int singleNonDuplicate(vector<int>& nums)
{
int left = 0, right = nums.size() - 1, mid;
while (left < right) {
mid = left + (right - left) / 2;
if (mid % 2 == 0) {
if (nums[mid] == nums[mid + 1]) {
left = mid + 1;
}
else {
right = mid - 1; //error
}
}
else {
if (nums[mid] == nums[mid - 1]) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
}
return nums[left];
}
};正确的代码
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
// 初始化左右指针，分别指向数组的起始和末尾
int left = 0, right = nums.size() - 1, mid;
// 当左指针小于右指针时，继续二分查找
while (left < right) {
// 计算中间索引，避免溢出使用 left + (right - left) / 2
mid = left + (right - left) / 2;
// 判断 mid 的奇偶性
if (mid % 2 == 0) { // 如果 mid 是偶数
// 检查当前元素是否与其后一个元素相同
if (nums[mid] == nums[mid + 1]) {
// 如果相等，说明左侧（包括 mid）均为成对元素，单独元素在右侧
left = mid + 1;
} else {
// 如果不相等，说明单独元素可能在左侧（含 mid），调整右边界
right = mid;
}
} else { // 如果 mid 是奇数
// 检查当前元素是否与其前一个元素相同
if (nums[mid] == nums[mid - 1]) {
// 如果相等，说明左侧（包括 mid）均为成对元素，单独元素在右侧
left = mid + 1;
} else {
// 如果不相等，说明单独元素可能在左侧，调整右边界
right = mid - 1;
}
}
}
// 当循环结束时，left 和 right 相遇，此时指向的就是单独元素
return nums[left];
}
};为什么错了？
因为单独元素的位置必定是偶数序列，所以当 mid 为偶数且 nums[mid] != nums[mid+1] 时，错误地将 right 设为 mid-1，从而排除了可能包含单独元素的中间位置。正确的做法应将 right 设为 mid，以确保搜索范围包含当前 mid。
3、解题思路：
注：因为数组是有序的，所以相同的元素肯定是相邻的。而那个单一的元素会出现的位置，可能在某个偶数索引的位置，单独元素出现之前，所有的元素都是两两出现的，且偶数索引和奇数索引的元素相同。比如，索引0和1相同，2和3相同，等等。而一旦出现了一个单独的元素，那么之后的元素对会被打乱。所以，二分查找的关键在于，通过中间元素的位置，判断当前这对是否是正常的。如果是，则说明问题出在后面；否则，问题出在前面。
- 初始化 ：设置左右指针分别指向数组的起始和末尾。
- 循环条件 ：当左指针小于右指针时，计算中间指针。
- 判断中间元素的奇偶性 ：
- 如果中间索引是偶数，检查该元素是否与其后一个元素相同。若相同，说明左侧均为成对元素，移动左指针；否则，右侧可能存在单独元素，调整右指针。
- 如果中间索引是奇数，检查该元素是否与其前一个元素相同。若相同，说明左侧均为成对元素，移动左指针；否则，调整右指针。
- 终止条件 ：当左右指针相遇时，返回当前元素即为单独元素。也就是
left < right，而且，这样写也有一个好处，那就是能确保循环只在有效范围内执行。当left和right相遇时，循环终止，此时直接返回nums[left]，避免出现数组越界问题。
