1.题目基本信息
1.1.题目描述
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
1.2.题目地址
https://leetcode.cn/problems/single-element-in-a-sorted-array/description/
2.解题方法
2.1.解题思路
二分查找（红蓝染色法）
2.2.解题步骤
第一步，确定红蓝染色的特征。特征一：红：位置i处值与处于同一对的元素相等；蓝：位置i处值与处于同一对的元素不相等（如果i为奇数，相邻元素取右边的偶数，反之取左边边的奇数）。特征二：左闭右开，left-1始终指向红色，right始终指向蓝色。
第二步，标准的左闭右开二分步骤。
注意：标准的二分模板会出现索引超范围问题，为了解决超限问题，可以在尾部添加一个不能取到的值。
3.解题代码
Python代码
class Solution:# 二分查找（红蓝染色法）# 第一步，确定红蓝染色的特征。特征一：红：位置i处值与处于同一对的元素相等；蓝：位置i处值与处于同一对的元素不相等（如果i为奇数，相邻元素取右边的偶数，反之取左边边的奇数）。特征二：左闭右开，left-1始终指向红色，right始终指向蓝色。# 第二步，标准的左闭右开二分步骤。# 注意：标准的二分模板会出现索引超范围问题，为了解决超限问题，可以在尾部添加一个不能取到的值。def singleNonDuplicate(self, nums: List[int]) -> int:# 红：i与相邻的对元素相等；蓝：i与相邻元素不相等（如果i为奇数，相邻元素取右边的偶数，反之取左边的奇数）。为了解决超限问题，在尾部添加一个哑结点length=len(nums)nums.append(-1)left,right=0,lengthwhile left<right:mid=(right-left)//2+left# neighIndex=mid+1 if mid%2==0 else mid-1neighIndex=mid^1if nums[mid]==nums[neighIndex]:left=mid+1else:right=midreturn nums[left]
C++代码
class Solution {
public:int singleNonDuplicate(vector<int>& nums) {int length=nums.size();nums.push_back(-1);int left=0,right=length;while(left<right){int mid=(right-left)/2+left;int neighIndex=mid%2==0 ? mid+1 : mid-1;if(nums[mid]==nums[neighIndex]){left=mid+1;}else{right=mid;}}return nums[left];}
};
4.执行结果
