540.Single Element in a Sorted Array
===

###### tags: `Medium`,`Array`,`Binary Search`

[540. Single Element in a Sorted Array](https://leetcode.com/problems/single-element-in-a-sorted-array/)

### 題目描述

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

Return *the single element that appears only once.*

Your solution must 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^

### 解答
#### C++

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int L = 0, R = nums.size() - 1;
        while (L < R) {
            int M = (L + R) / 2;
            if (nums[M] == nums[M-1]) {
                if ((M - L) & 1) L = M + 1;
                else R = M - 2;
            } else {
                if ((M - L) & 1) R = M - 1;
                else L = M;
            }
        }
        return nums[L];
    }
};

> [name=Yen-Chi Chen][time=Tue, Feb 21, 2023]

#### Python

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        L, R = 0, len(nums) - 1
        while L < R:
            M = (L + R) // 2
            if nums[M] == nums[M-1]:
                if (M - L) & 1: L = M + 1
                else: R = M - 2
            else:
                if (M - L) & 1: R = M - 1
                else: L = M
        return nums[L]

> [name=Yen-Chi Chen][time=Tue, Feb 21, 2023]

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

        while l < r:
            m = l + (r - l) // 2
            n = m - 1 if m % 2 else m + 1
            if nums[m] != nums[n]:
                r = m
            else:
                l = m + 1

        return nums[l]

> [name=Ron Chen][time=Wed, Feb 22, 2023]

#### Javascript
##### 思路：
因為只有一個數字出現一次，所以`nums.length`一定是奇數，做binary search切下去剛好就是正中間。
`i = (0 + nums.length - 1) / 2`
1. `i`為奇數
nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
前後的數字數量為偶數，如果`nums[i] == nums[i-1]`，那前面剩下的數量就是奇數，一定會有一個數字落單，所以要找的數字就在`i`前面，反之亦然。

2. `i`為偶數
nums = [3, 3, 7, 7, 10, 11, 11]
前後的數字數量為奇數，如果`nums[i] == nums[i-1]`，那前面剩下的數量就是偶數，那要找的數字就在`i`後面了。

function singleNonDuplicate(nums) {
  let max = nums.length - 1;
  let min = 0;
  while (max >= min) {
    const mid = ~~((max + min) / 2);
    if (nums[mid] !== nums[mid + 1] && nums[mid] !== nums[mid - 1]) {
      return nums[mid];
    }

    if (mid % 2 === 0) {
      if (nums[mid] === nums[mid + 1]) {
        min = mid + 1;
      }
      if (nums[mid] === nums[mid - 1]) {
        max = mid - 1;
      }
    } else {
      if (nums[mid] === nums[mid + 1]) {
        max = mid - 1;
      }
      if (nums[mid] === nums[mid - 1]) {
        min = mid + 1;
      }
    }
  }
}

> 我寫得真是醜...
> [name=Marsgoat][time=Tue, Feb 21, 2023]

function singleNonDuplicate(nums) {
  let max = nums.length - 1;
  let min = 0;
  while (max > min) {
    const mid = ~~((max + min) / 2);
    if (nums[mid] === nums[mid ^ 1]) {
      min = mid + 1;
    } else {
      max = mid;
    }
  }

  return nums[min];
}

> copilot教我寫的，順手分享一下，真的是簡約而不簡單。
> [name=Marsgoat][time=Tue, Feb 21, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)