来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array
题目描述
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 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 <= 105 0 <= nums[i] <= 105
解题思路
本题难点在于限制了时间复杂度和空间复杂度，根据时间复杂度来看，很明显在诱导解题者使用二分法解题。
首先寻找规律，单一元素a的左边必然有偶数个元素，所以a的坐标必然是偶数，并且，a左边偶数坐标left的值均与left+1的值相同，右边偶数坐标right的值与right-1的值相同，所以，只需要找到这个分界点就是单一元素。
使用二分法，左边界left设置为0，右边界right设置为最大的偶数坐标，求出中间的偶数坐标mid（如果是奇数需要-1变成偶数坐标）判断是否nums[mid] == nums[mid + 1],如果相同，则a在mid的右边，并且mid不可能为单一元素，将left设置为mid + 2；否则，a可能在mid左边，也可能就是mid，所以将right设置为mid。
代码展示
class Solution { public: int singleNonDuplicate(vector<int>& nums) { int iLeft = 0, iRight = nums.size() - 1, iMid = 0; if(iRight % 2) iRight--; while(iLeft < iRight) { iMid = (iLeft + iRight) / 2; if(iMid % 2) iMid --; if(nums[iMid] == nums[iMid + 1]) iLeft = iMid + 2; else iRight = iMid; } return nums[iLeft]; } };
运行结果
