# 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];
  }
}
```