目录

1. 题目描述

2. 解题分析

2.1 思路1

2.2 思路2

left和right的更新

边界情况处理

3. 代码实现

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

提示:
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5
 
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

2.1 思路1

        一个数与自己进行按位异或运算会得到0。所以，只要将数组中的所有数都做按位异或运算就最后所得的结果就是所要求的那个单一元素。

        直观的做法（假定该数组为a）就是，a(0)和a(1)做异或运算，其结果再与a[2]做异或运算，。。。，直到最后与a[N-1]做异或运算，即得到所求结果。但是这样的实现，虽然空间复杂度满足O(1)的要求，时间复杂度需要O(N)的运算复杂度，不满足题目要求的O(log(N))复杂度的要求。

2.2 思路2

        由于要求时间复杂度为O(log(N))，所以很自然地可以想象到二分法（除了二分法还有什么能够有O(log(N))的时间复杂度呢？）。题设中已经明确了输入数组是有序数组，所以出现两次的数一定是相邻出现的，孤独数与其前面的数和后面的数都不相同。而数组中的其它数都或者和它前面的数相同或者和它后面的数相同。基于这一点我们可以基于二分法来寻找该孤独数。

left和right的更新

        二分法搜索的关键点在于left和right的更新。常规的二分法中取mid=(left+right)//2("//" means integer division in python)即可。而本题中关于mid的处理也有一点点特殊。

        由于孤独数的前面必定有偶数个数，其后也必定有偶数个数，所以孤独数的下标（考虑从0开始的zero-indexing）必定为偶数。因此如果mid=(left+right)//2为奇数的话，可以取mid=mid-1调整为偶数来处理。

        对于某个mid，如果nums[mid]和它前面的数以及它后面的数都不相等的话，那它就是所要找的数。如果不是的话，那搜索区间是取左半区还是右半区呢？

        如果，nums[mid]等于nums[mid-1]的话，由于右半区为偶数个数，唯一的孤独数不可能出现在偶数个数中，因此下一步应该搜索左半区。此时，应该保持left不变，而将right更新为mid（注意，不是mid-1，因为必须要保持搜索区间长度为奇数。这也是本题与一般的二分法略有不同的地方）。

        反之，如果nums[mid]等于nums[mid+1]的话，下一步应该搜索右半区。此时应该保持right不变，而将left更新为mid。

边界情况处理

       以上处理中要比较nums[mid]，nums[mid-1] 以及nums[mid+1]。当mid=0或者mid=N-1时，需要进行适当的边界处理以避免越界错误。

        当然，也不要忘了，只有一个数输入的情况。

        此外，输入数组长度为偶数的情况属于异常情况，需要考虑把输入合法性检查考虑进去。

3. 代码实现

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        N     = len(nums)        
        if N==1:
            return nums[0]
        if N%2 == 0:
            return None
        left  = 0
        right = N - 1
        
        # Boundary check
        if nums[0] != nums[1]:
            return nums[0]
        if nums[-1] != nums[-2]:
            return nums[-1]        
        cnt = 0                
        while left <= right:
            if left == right:
                return nums[left]

            mid   = (left+right) // 2
            # print(left,right,mid)
            if mid%2 == 1:
                mid = mid - 1            

            if (nums[mid] != nums[mid-1]) and (nums[mid] != nums[mid+1]):
                return nums[mid]
            
            if nums[mid] == nums[mid-1]:
                right = mid
            else:
                left  = mid   

if __name__ == '__main__':        
    
    sln = Solution()

    nums = [1,1,2,3,3,4,4,8,8]
    print(sln.singleNonDuplicate(nums))            
    
    nums = [3,3,7,7,10,11,11]
    print(sln.singleNonDuplicate(nums))            
    
    nums = [3,3,7,7,9,9,10]
    print(sln.singleNonDuplicate(nums))            
    
    nums = [2,3,3,4,4,8,8]
    print(sln.singleNonDuplicate(nums))            
        
    nums = [2]
    print(sln.singleNonDuplicate(nums))            
    
    nums = [2,2,3,3]
    print(sln.singleNonDuplicate(nums))