540. Single Element in a Sorted Array.md

540. Single Element in a Sorted Array

https://leetcode.com/problems/single-element-in-a-sorted-array/

solution

• 有序数组查找问题，一般想到二分。和邻居比较来判断位于左右哪边.
• 单独出现的元素其左边有偶数个元素，因此其下标index 为偶数
  • mid为偶数，如果 mid与mid+1值相等，则l=mid+2; 如果mid与mid+1不等，则r=mid
  • mid为奇数，mid-1变为偶数

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l = 0
        r = len(nums) - 1

        while l < r:
            mid = l + (r - l) // 2
            if mid % 2 == 1:
                mid -= 1

            if nums[mid] == nums[mid+1]:
                l = mid + 2
            else:
                r = mid
        return nums[l]

时间复杂度：O(log(n))
空间复杂度：O(1)