二分查找.540. 有序数组中的单一元素

题目描述

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例

示例 1:

输入: [1,1,2,3,3,4,4,8,8] 输出: 2 示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这道题巧妙之处在于，如果所有元素都是出现两次，那么对于任意的 i & 1 == 1, 存在 A[i] == A[i+1]
而插入一个单一的数字之后，会出现什么现象呢？
那就以上规律在左边依然适用，在右边却不适用了

代码

lass Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        # 二分
        l, r = 0, len(nums)-1
        while l < r:
            mid = (l+r) // 2
            if mid & 1:
                mid -= 1
            if nums[mid] == nums[mid+1]:
                l = mid + 2
            else:
                r = mid
        return nums[l]

复杂度分析

• 时间复杂度：O(logn)
• 空间复杂度：O(1)