🥈540. 有序数组中的单一元素

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。请你找出并返回只出现一次的那个数。你设计的解决方案必须满足时间复杂度和 空间复杂度。

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10

提示:

题解

一看时间复杂度是，估计就是二分了，结果想的还是不对❎啊！好蠢！

全数组的二分查找

假设只出现一次的元素位于下标x，由于其余每个元素都出现两次，因此下标x的左边和右边都有偶数个元素，数组的长度是奇数。

nums = [3,3,7,7,10,11,11];

以数组nums为例，由于数组是有序的，因此数组中相同的元素一定相邻。对于下标x左边的下标y，如果nums[y]=nums[y+1]（比如nums[0]=nums[1]=3，nums[2]=nums[3]=7），则y 一定是偶数；对于下标x右边的下标 z，如果 nums[z]=nums[z+1]（比如nums[5]=nums[6]=11），则 z 一定是奇数。由于下标x是相同元素的开始下标的奇偶性的分界，因此可以使用二分查找的方法寻找下标x。

初始时，二分查找的左边界是0，右边界是数组的最大下标。每次取左右边界的平均值mid作为待判断的下标，根据mid的奇偶性决定和左边或右边的相邻元素比较：

如果mid是偶数，则比较 nums[mid] 和 nums[mid+1]是否相等；如果 mid 是奇数，则比较
nums[mid−1] 和 nums[mid] 是否相等。

如果上述比较相邻元素的结果是相等，则
mid
<
�
midmid
≥
�
mid≥x，调整右边界。调整边界之后继续二分查找，直到确定下标
�
x 的值。

得到下标
�
x 的值之后，
nums
[
�
]
nums[x] 即为只出现一次的元素。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/solution/you-xu-shu-zu-zhong-de-dan-yi-yuan-su-by-y8gh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。