# 540 Single Element in a Sorted Array

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

## 1. Question

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

**Example 1:**

```
Input: [1,1,2,3,3,4,4,8,8]

Output: 2
```

**Example 2:**

```
Input: [3,3,7,7,10,11,11]

Output: 10
```

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

## 2. Implementation

**(1) Binary Search**

思路：用二分法的思想，中点mid，有三种情况\
1\. 如果nums\[mid - 1] == nums\[mid], 判断mid - 2 + 1(因为数组从0开始)是否奇数，如果是，则出现一次的数在\[start, mid - 2]之间，否则在\[mid + 1, end]之间

1. 和情况一类似，如果nums\[mid] == nums\[mid + 1] ，判断mid - 1 + 1是否奇数，是的话则答案在\[start, mid - 1]之间，否则在\[mid + 2, end]之间
2. 情况三，当nums\[mid] != nums\[mid - 1] 且 nums\[mid] != nums\[mid + 1]时，nums\[mid]就是我们要找的数

```java
public class Solution {
    public int singleNonDuplicate(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return -1;
        }

        int start = 0, end = nums.length - 1, mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;

            if (nums[mid - 1] == nums[mid]) {
                if ((mid - 2 + 1)  % 2 != 0) {
                    end = mid - 2;
                }
                else {
                    start = mid + 1;
                }
            }
            else if (nums[mid] == nums[mid + 1]) {
                if ((mid - 1 + 1) % 2 != 0) {
                    end = mid - 1;
                }
                else {
                    start = mid + 2;
                }
            }
            else {
                return nums[mid];
            }
        }

        if (start > 0 && nums[start - 1] != nums[start]) {
            return nums[start];
        }
        else {
            return nums[end];
        }
    }
}
```

## 3. Time & Space Complexity

**Binary Search:** 时间复杂度O(logn), 空间复杂度O(1)