# 540.Single-Element-in-a-Sorted-Array

## 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. 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
```

## 代码

### Approach 0: use XOR

O(n)

```java
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int res = 0;
        for (int num : nums) {
            res ^= num;
        }
        return res;
    }
}
```

### Approach 1: Binary Search

O(logN)

```java
class Solution {
  public int singleNonDuplicate(int[] nums) {
        int lo = 0;
    int hi = nums.length - 1;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      // 0: 前一个数组为奇数，1：前一个数组为偶数
      boolean halvesAreEven = (hi - mid) % 2 == 0;
      if (nums[mid] == nums[mid + 1]) {
        if (halvesAreEven) { 
// Case 1: Mid’s partner is to the right, and the halves were originally even
          lo = mid + 2; 
        } else {
// Case 2: Mid’s partner is to the right, and the halves were originally odd
          hi = mid - 1;    
        }
      } else if (nums[mid - 1] == nums[mid]) {
        if (halvesAreEven) {
// Case 3: Mid’s partner is to the left, and the halves were originally even
          hi = mid - 2; 
        } else {
// Case 4: Mid’s partner is to the left, and the halves were originally odd
          lo = mid + 1;
        }
      } else {
        return nums[mid];
      }
    }

    return nums[lo];
  }
}
```

Approach #3 Binary Search on Evens indexes Only

O(logN)

```java
class Soluton {
  public int singleNonDuplicate(int[] nums) {
    int lo = 0;
    int hi = nums.length - 1;
    while (lo < hi) {
      int mid = lo + (hi - lo) / 2;
      if (mid % 2 == 1) mid--;
      if (nums[mid] == nums[mid + 1]) {
        lo = mid + 2;
      } else {
        hi = mid;
      }
    }
    return nums[lo];
  }
}
```


---

# 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://wentao-shao.gitbook.io/leetcode/array/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.