# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/leetcode/binary-search/540-single-element-in-a-sorted-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.