Single Element in a Sorted Array

Description

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

Follow up: Your solution should run in O(log n) time and O(1) space.

 

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

 

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

Solution(javascript)

/*
 * @lc app=leetcode id=540 lang=javascript
 *
 * [540] Single Element in a Sorted Array
 */

// @lc code=start
/** 观察下标，单个元素的那里是个分隔点，可以用 Binary Search
 * @param {number[]} nums
 * @return {number}
 */
const singleNonDuplicate = function (nums) {
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    const middle = Math.floor((left + right) / 2)
    if (nums[middle] !== nums[middle - 1] && nums[middle] !== nums[middle + 1]) {
      return nums[middle]
    }
    if (middle % 2 === 1) {
      if (nums[middle] === nums[middle - 1]) {
        left = middle + 1
      } else {
        right = middle - 1
      }
    } else if (nums[middle] === nums[middle + 1]) {
      left = middle + 1
    } else {
      right = middle - 1
    }
  }
  return -1
}