540-有序数组中的单一元素

[YBFACC]

540-有序数组中的单一元素

思路

• 要去：O(log n)时间复杂度和 O(1)空间复杂度

• 基础思路：二分

• 如果mid左右都不存在与mid重复的数，则找到目标数

• mid左找到与mid重复的数

  • 判断mid左边数组的长度-1是不是奇数
  1. 是，则舍去右边。right=mid-2
  2. 否，则舍去左边。left=mid+1

• mid右找到与mid重复的数

  • （同理推导）

• 如果最后left=right，则找到目标数

代码

var singleNonDuplicate = function (nums) {
  if (nums.length === 0) return null
  let left = 0
  let right = nums.length - 1
  while (left <= right) {

    if (left === right) return nums[left]

    let mid = (left + right) >> 1
    if (nums[mid] === nums[mid - 1]) {
      if ((mid - left - 1) % 2 === 1) {
        right = mid - 2
      } else {
        left = mid + 1
      }
    } else if (nums[mid] === nums[mid + 1]) {
      if ((right - mid - 1) % 2 === 1) {
        left = mid + 2
      } else {
        right = mid - 1
      }
    } else {
      return nums[mid]
    }
  }
}