# 540. Single Element in a Sorted Array

[https://leetcode.com/problems/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变为偶数

```python
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)
