原题地址（中等）

方法1—二分查找

思路

这题遍历一次进行查找肯定是最简单的方法，但是时间复杂度为 O(N) ，不符合题意。
一看到时间复杂度要求 O(logN) ，自然而然就想到二分查找。

但是二分查找需要有条件进行判断，此题判断的条件是什么呢？
**
单一元素在哪里？无非就以下几种情况：

  1. nums=[1,2,2,3,3,4,4,8,8] ；
  2. nums=[1,1,2,3,3,4,4,8,8] ；
  3. nums=[1,1,2,2,3,4,4,8,8] ；
  4. nums=[1,1,2,2,3,3,4,8,8] ；
  5. nums=[1,1,2,2,3,3,4,4,8] ；

我们用二分法把数组一分为二，无非就两种情况：

  1. 正常情况，比如[1,1,2,2] ; [3,3,4,4,8] 这种直接进入第二个区间就行了；
  2. 不正常情况，比如[1,1,2] ; [2,3,4,4``] ，也就是两个相同的数字被划分到了两侧。这种情况进入哪个区间都不会得到答案，因为这种划分就是错误的。所以我们应该把 2 划分到一起，这样就成了第一种正常情况了。

把不正常情况变成了正常情况，我们就只关注正常情况，看看怎么样进行二分查找。

很明显，判断的条件就是左右区间内元素个数的奇偶性。**

按照题意， nums 数组中一定是奇数个元素，把数组一分为二，两边元素个数肯定一边是奇数，一边是偶数。然后将区间缩小到奇数的那一边，重复上述操作。
**

代码

先写出二分查找模板
关于二分查找模板，我写了一篇文章。
二分查找模板

  1. class Solution:
  2.     def singleNonDuplicate(self, nums: List[int]) -> int:
  3.         n = len(nums)
  4.         low, high = 0, n-1
  6.         while low < high:
  7.             mid = low + (high -low) // 2
  9.             # 此处处理不正常情况
  11.             if 左边偶数个元素
  12.                 low = mid + 1
  13.             else:
  14.                 high = mid
  16.         return nums[low]

**
处理不正常情况有两种选择， mid+1 或者 mid-1 ，在此我们选择 mid-1 ，这是由于二分查找模板的性质决定的。

注意，这个模板 low=mid+1 ，但是 high=mid ，所以如果有 low==mid 的情况出现，也没关系，更新仍会继续。但是如果出现 high==mid 的情况出现，就有可能进入死循环。

举反例： nums=[3,3,7,7,10,11,11] 。按照 mid+1 ，最后会进入 low 指向 10 ， high 指向第二个11的情况，这时 mid 为第一个 11 ，切分为 [10, 11], [11] ，是不正常情况，执行 mid+1 ，这时 mid==high ，你会发现进入死循环了。

所以我们处理不正常情况，选择的是让 mid-1 

  1. class Solution:
  2.     def singleNonDuplicate(self, nums: List[int]) -> int:
  3.         n = len(nums)
  4.         low, high = 0, n-1
  6.         while low < high:
  7.             mid = low + (high -low) // 2
  8.             if mid > 0 and nums[mid] != nums[mid-1]:  ## 如果是不正常情况
  9.                 mid -= 1
  10.             # 左边元素下标[low, mid]， 右边元素下标[mid+1, high]
  11.             if (mid-low+1) % 2 == 0:  # 左边偶数个元素
  12.                 low = mid + 1
  13.             else:
  14.                 high = mid
  16.         return nums[low]

时空复杂度

O(log n)时间复杂度和 O(1)空间复杂度，满足题意。
**

**