# Single Element in a Sorted Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/single-element-in-a-sorted-array)
Canonical: https://scaleengineer.com/dsa/problems/single-element-in-a-sorted-array
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Infosys](https://scaleengineer.com/companies/infosys), [Nvidia](https://scaleengineer.com/companies/nvidia), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Snowflake](https://scaleengineer.com/companies/snowflake), [tcs](https://scaleengineer.com/companies/tcs), [Coupang](https://scaleengineer.com/companies/coupang), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Pinterest](https://scaleengineer.com/companies/pinterest), [Moloco](https://scaleengineer.com/companies/moloco), [blinkit](https://scaleengineer.com/companies/blinkit)
---
## Problem
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 <= 105`
* `0 <= nums[i] <= 105`

# Approaches
## Brute Force Linear Scan
This approach involves iterating through the sorted array and comparing adjacent elements. Since every element appears twice except for one, the pairs of identical numbers will be next to each other. We can check elements in pairs to find the one that breaks the pattern.
**Time:** O(n) - In the worst-case scenario, we might have to traverse the entire array to find the single element (e.g., when it's the last element). · **Space:** O(1) - We only use a constant amount of extra space for loop variables.
**Pros:** Very simple to understand and implement.
**Cons:** Inefficient for large inputs.; Does not meet the O(log n) time complexity requirement specified in the problem.
### Explanation
The algorithm iterates through the array with a step of 2. For each index `i`, it compares `nums[i]` with `nums[i+1]`. If they are different, `nums[i]` must be the single element because all preceding elements formed valid pairs. If the loop completes, the single element must be the last one in the array.

```java
class Solution {
    public int singleNonDuplicate(int[] nums) {
        // Handle the edge case of a single element array
        if (nums.length == 1) {
            return nums[0];
        }

        // Iterate through the array by pairs
        for (int i = 0; i < nums.length - 1; i += 2) {
            // If a pair doesn't match, the first element is the single one
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }

        // If the loop finishes, the single element is the last one
        return nums[nums.length - 1];
    }
}
```
### Algorithm
*   Iterate through the array from index 0 to `n-2` with a step of 2.
*   At each step `i`, compare `nums[i]` and `nums[i+1]`.
*   If `nums[i] != nums[i+1]`, then `nums[i]` is the unique element. Return it.
*   If the loop finishes, the last element `nums[n-1]` is the unique one. Return it.

## Bitwise XOR
This clever approach uses the properties of the bitwise XOR operator. XORing a number with itself results in 0 (`a ^ a = 0`), and XORing a number with 0 leaves the number unchanged (`a ^ 0 = a`). By XORing all numbers in the array, all the duplicate pairs will cancel each other out, leaving only the single, non-duplicated element.
**Time:** O(n) - We must iterate through every element in the array once. · **Space:** O(1) - Only a single integer variable is used to store the cumulative XOR result.
**Pros:** Elegant and concise.; Works even if the array is not sorted.
**Cons:** Does not utilize the sorted property of the array.; Fails to meet the O(log n) time complexity requirement.
### Explanation
We initialize a variable, say `uniqueElement`, to 0. Then, we iterate through the `nums` array. In each iteration, we perform a bitwise XOR operation between `uniqueElement` and the current number, and store the result back in `uniqueElement`. After the loop, `uniqueElement` will hold the value of the single number that appears only once.

```java
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int uniqueElement = 0;
        for (int num : nums) {
            uniqueElement ^= num;
        }
        return uniqueElement;
    }
}
```
### Algorithm
*   Initialize a variable `result` to 0.
*   Iterate through each number `num` in the input array `nums`.
*   Update `result` by XORing it with the current number: `result = result ^ num`.
*   After the loop, `result` will contain the single non-duplicate element. Return `result`.

## Optimized Binary Search
The most efficient approach leverages the fact that the array is sorted. We can use binary search to find the single element in logarithmic time. The core idea is to observe the indices. Before the single element, every pair `(nums[i], nums[i+1])` starts at an even index `i`. After the single element, this pattern is disrupted, and pairs start at an odd index. We can use this property to decide which half of the array to search next.
**Time:** O(log n) - Standard binary search halves the search space in each iteration. · **Space:** O(1) - No extra space proportional to the input size is used.
**Pros:** Extremely efficient, meeting the problem's time and space constraints.; Effectively uses the sorted property of the array.
**Cons:** The logic is more complex to devise and implement correctly compared to linear scans.
### Explanation
We perform a binary search on the array indices. Let `low = 0` and `high = n-1`. In each step, we calculate `mid`. We need to check the element at `mid` and its pair. To simplify, we can ensure `mid` is always an even index. If `mid` is odd, we decrement it by one. Now, we compare `nums[mid]` and `nums[mid+1]`. 
- If `nums[mid] == nums[mid+1]`, it means the array up to `mid+1` is 'correct' (all elements form pairs), so the single element must be in the right half. We update `low = mid + 2`.
- If `nums[mid] != nums[mid+1]`, it means the disruption (the single element) is in the left half (including `mid`). We update `high = mid`.
The loop continues until `low` and `high` converge, at which point `nums[low]` is our answer.

```java
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int low = 0;
        int high = nums.length - 1;

        while (low < high) {
            int mid = low + (high - low) / 2;
            // We want to check pairs, so we need to ensure mid is at an even index.
            // If mid is odd, its pair is at mid-1. If mid is even, its pair is at mid+1.
            // Let's make mid always point to the first element of a pair.
            if (mid % 2 == 1) {
                mid--;
            }

            // If the elements at mid and mid+1 are the same, it means the single element
            // is not in the left part (including mid and mid+1). So we search on the right.
            if (nums[mid] == nums[mid + 1]) {
                low = mid + 2;
            } 
            // If they are different, the single element is in the left part (including mid).
            else {
                high = mid;
            }
        }
        // When low == high, we have found the index of the single element.
        return nums[low];
    }
}
```
### Algorithm
*   Initialize search boundaries `low = 0` and `high = nums.length - 1`.
*   Loop while `low < high`.
*   Calculate `mid = low + (high - low) / 2`.
*   To ensure we are always looking at the start of a pair, if `mid` is odd, adjust it: `mid--`.
*   Check if the pair at `(mid, mid+1)` is a valid pair (`nums[mid] == nums[mid+1]`).
*   If it is a valid pair, the single element must be in the right half. Set `low = mid + 2`.
*   If it is not a valid pair, the single element is in the left half (including `mid`). Set `high = mid`.
*   When the loop terminates (`low == high`), `nums[low]` is the single element. Return it.

# Solutions
### Java

```java
class Solution {
public
  int singleNonDuplicate(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
      int mid = (left + right) >> 1;
```

### CPP

```cpp
class Solution {
public:
  int singleNonDuplicate(vector<int> &nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
      int mid = left + right >> 1;
      if (nums[mid] != nums[mid ^ 1])
        right = mid;
      else
        left = mid + 1;
    }
    return nums[left];
  }
};

```

### Python

```python
class Solution : def singleNonDuplicate ( self , nums : List [ int ]) -> int : left , right = 0 , len ( nums ) - 1 while left < right : mid = ( left + right ) >> 1 # Equals to: if (mid % 2 == 0 and nums[mid] != nums[mid + 1]) or (mid % 2 == 1 and nums[mid] != nums[mid - 1]): if nums [ mid ] != nums [ mid ^ 1 ]: right = mid else : left = mid + 1 return nums [ left ]
```