二分查找应用---有序数组中的单一元素
前言
大家好，我是程序员小熊，来自大厂的程序猿。了解二分查找的童鞋，都知道二分查找常用于在有序数组中查找某一特定元素，而且很多童鞋也都知道二分查找的模板该怎么写。
今天小熊带来一道亚马逊的面试题，也就是力扣540. 有序数组中的单一元素，这道题难度为中等，采用“二分查找 + 动图”的方式深入剖析，供大家参考，希望对大家有所帮助。
题目
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: [3,3,7,7,10,11,11]
输出: 10
注意: 您的方案应该在 O(log n)时间复杂度
和 O(1)空间复杂度中运行。
解题思路
本题如果不要求解法的时间复杂度为 O(log n) 的话，就跟力扣136. 只出现一次的数字差不多，只是后者不要求数组是有序的，但解法一样，可以通过异或去做，因为一个数字跟自身相异或，结果为 0；但异或 0，结果为自身，因此让数组中所有元素都相互异或即可得到结果，但时间复杂度为 O(n)。
由于题目明确要求解法的时间复杂度为 O(log n)，对二分查找有所了解的童鞋，很自然地会想到需要采用二分查找法去做。
那具体如何通过二分查找去做呢？见下面例子。
举例
以数组 [3,3,7,7,10,11,11] 为例子，如下图示。
示例
二分查找一般通过数组的中间元素 nums[mid] 判断 target 的位置（在 mid 位置，亦或是在 mid 的左侧或右侧），本题也不例外。
确定中间元素
由题意可知，数组长度一定为奇数，因此可以进行如下操作：
- 1、判断中间元素是否跟两侧元素相等；
- 2、若等于任意一侧元素，则去掉中间元素及其跟它相等的元素，将原数组分为两部分（奇数长度和偶数长度），由于唯一的那个数一定存在于奇数长度的数组，因此丢弃偶数长度的子数组，在奇数长度的子数组中重复1和2；
- 3、若不等于两侧元素，则中间元素就是要查找的只出现一次的那个数字。
如下图示：
1、判断 nums[mid] == nums[mid - 1]；
2、移除 nums[mid] 和 nums[mid - 1]；
3、判断拆分后的两数组的长度，并移除偶数长度子数组；
4、在奇数长度的子数组中重复前1、2、3步；
查找过程完整动态展示
动态如下：
Show me the Code
C
int singleNonDuplicate(int* nums, int numsSize){
int left = 0, right = numsSize - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
/* 判断（子）数组的长度，进而确认 target 位置 */
bool halvesAreEven = (right - mid) % 2 == 0;
/* 中间元素等于右边元素 */
if (nums[mid + 1] == nums[mid]) {
/* halvesAreEven 为偶数，mid 右侧存在 target */
if (halvesAreEven) {
left = mid + 2;
/* halvesAreEven 为奇数，mid 左侧存在 target */
} else {
right = mid - 1;
}
/* 中间元素等于左侧元素 */
} else if (nums[mid - 1] == nums[mid]) {
/* halvesAreEven 为偶数，mid 左侧存在 target */
if (halvesAreEven) {
right = mid - 2;
/* halvesAreEven 为奇数，mid 右侧存在 target */
} else {
left = mid + 1;
}
/* 中间元素跟左右侧元素都不等，中间元素是target */
} else {
return nums[mid];
}
}
return nums[left];
}
简化
上面的代码略显冗余，if 跟 else if 中均需要先判断 nums[mid] 与两侧的元素是否相等，再判断 halvesAreEven 是否为奇数，然后决定在 mid 的左侧还是右侧查找，有没有简便一点的方法？
答案是有的。
- 1、将 nums[mid + 1]、nums[mid - 1] 与 nums[mid] 比较，简化为 nums[temp] 与 nums[mid] 比较，其中 temp = mid ^ 1，若相等则左边界 left 右移（left = mid + 1）继续查找；
- 2、若不相等，则相当于 nums[mid] 与左右两侧元素都不相等，相当于 mid 就是待查找的只出现一次的那个数字。
举例
以数组 [1,1,2,3,3,4,4] 为例子，如下动图示。
示例动图
Show me the Code
C++
int singleNonDuplicate(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int temp = mid ^ 1;
if (nums[mid] == nums[temp]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
Golang
func singleNonDuplicate(nums []int) int {
left, right := 0, len(nums) - 1
for left < right {
mid := left + (right - left) / 2;
temp := mid ^ 1;
if nums[mid] == nums[temp] {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left]
}
Python3
def singleNonDuplicate(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (right + left) // 2;
temp = mid ^ 1;
if nums[mid] == nums[temp]:
left = mid + 1
else:
right = mid
return nums[left]
复杂度分析
空间复杂度：O(1)，未开辟额外存储空间。
时间复杂度：O(logn)，n 为数组长度。
腾讯云开发者
