# LeetCode 540: Single Element in a Sorted Array

## Problem Restatement

We are given a sorted integer array `nums`.

Every element appears exactly twice, except one element that appears exactly once.

We need to return the single element.

The required solution must run in:

```python
O(log n)
```

time and:

```python
O(1)
```

space.

The sorted order is the key. Since equal values appear next to each other, every duplicated value forms an adjacent pair.

The official statement requires returning the element that appears only once, with every other element appearing exactly twice. The solution must use logarithmic time and constant space.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A sorted integer array `nums` |
| Output | The element that appears exactly once |
| Pair rule | Every other element appears exactly twice |
| Required time | `O(log n)` |
| Required space | `O(1)` |

Function shape:

```python
def singleNonDuplicate(nums: list[int]) -> int:
    ...
```

## Examples

Consider:

```python
nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]
```

Every number appears twice except:

```python
2
```

So the answer is:

```python
2
```

Another example:

```python
nums = [3, 3, 7, 7, 10, 11, 11]
```

The single element is:

```python
10
```

So the answer is:

```python
10
```

## First Thought: Linear Scan

Because the array is sorted, duplicates are adjacent.

So one simple method is to scan the array in steps of two:

```python
nums[0] with nums[1]
nums[2] with nums[3]
nums[4] with nums[5]
```

When we find a pair that does not match, the first element of that pair is the single element.

Example:

```python
[1, 1, 2, 3, 3]
```

Compare:

```python
nums[0] == nums[1]
```

Then compare:

```python
nums[2] != nums[3]
```

So `nums[2]` is the single element.

This works, but it takes `O(n)` time. The problem asks for `O(log n)`, so we need binary search.

## Key Insight

Before the single element, pairs start at even indices.

After the single element, pairs start at odd indices.

Example:

```python
[1, 1, 2, 3, 3, 4, 4]
```

Before the single element `2`:

```text
index 0, 1 -> pair 1, 1
```

The pair starts at even index `0`.

After the single element:

```text
index 3, 4 -> pair 3, 3
index 5, 6 -> pair 4, 4
```

The pairs start at odd indices.

So we can use index parity to decide which half contains the single element.

A clean way is to force `mid` to be even.

Then compare:

```python
nums[mid] == nums[mid + 1]
```

If they are equal, then the pair at `mid, mid + 1` is valid. The single element must be after this pair.

If they are not equal, then the pairing is broken at or before `mid`. The single element is at `mid` or to the left.

## Algorithm

Use binary search with two pointers:

```python
left = 0
right = len(nums) - 1
```

While `left < right`:

1. Compute `mid`.
2. If `mid` is odd, subtract `1` so that `mid` is even.
3. Compare `nums[mid]` and `nums[mid + 1]`.
4. If they are equal, move rightward:

```python
left = mid + 2
```

5. Otherwise, keep the left half:

```python
right = mid
```

When the loop ends, `left == right`.

That index is the single element.

## Correctness

The array consists of adjacent duplicate pairs and one single element.

Before the single element, the duplicate pairs occupy indices:

```text
(0, 1), (2, 3), (4, 5), ...
```

So each pair starts at an even index.

After the single element, the single element shifts the pairing by one position. Therefore, duplicate pairs start at odd indices.

During binary search, the algorithm always chooses an even `mid`.

If `nums[mid] == nums[mid + 1]`, then the pair beginning at `mid` is correctly aligned. That means the single element cannot be at or before `mid + 1`; otherwise this pair alignment would already be broken. So the algorithm safely discards the range through `mid + 1`.

If `nums[mid] != nums[mid + 1]`, then the pair starting at `mid` is not correctly aligned. This means the single element is either exactly at `mid` or lies before it. So the algorithm safely keeps the range ending at `mid`.

Each step preserves the invariant that the single element lies inside `[left, right]`.

When `left == right`, only one candidate remains. By the invariant, that candidate is the single element.

## Complexity

Let `n = len(nums)`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(log n)` | Binary search halves the search range |
| Space | `O(1)` | Only a few variables are used |

## Implementation

```python
class Solution:
    def singleNonDuplicate(self, nums: list[int]) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (left + right) // 2

            if mid % 2 == 1:
                mid -= 1

            if nums[mid] == nums[mid + 1]:
                left = mid + 2
            else:
                right = mid

        return nums[left]
```

## Code Explanation

We start with the whole array:

```python
left = 0
right = len(nums) - 1
```

The loop continues while more than one candidate remains:

```python
while left < right:
```

We compute the middle index:

```python
mid = (left + right) // 2
```

Then we force `mid` to be even:

```python
if mid % 2 == 1:
    mid -= 1
```

This lets us always compare a potential pair:

```python
nums[mid], nums[mid + 1]
```

If the pair is valid:

```python
if nums[mid] == nums[mid + 1]:
```

then the single element must be after it:

```python
left = mid + 2
```

Otherwise, the pairing has already broken:

```python
right = mid
```

At the end:

```python
return nums[left]
```

`left` points to the only remaining candidate.

## Alternative: XOR Trick

There is a clever linear-time solution using XOR.

```python
class Solution:
    def singleNonDuplicate(self, nums: list[int]) -> int:
        answer = 0

        for num in nums:
            answer ^= num

        return answer
```

This works because:

```python
x ^ x == 0
```

and:

```python
x ^ 0 == x
```

So all duplicated numbers cancel out.

However, this solution takes `O(n)` time, so it does not satisfy the problem's required `O(log n)` time.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.singleNonDuplicate([1, 1, 2, 3, 3, 4, 4, 8, 8]) == 2
    assert s.singleNonDuplicate([3, 3, 7, 7, 10, 11, 11]) == 10
    assert s.singleNonDuplicate([1]) == 1
    assert s.singleNonDuplicate([1, 2, 2, 3, 3]) == 1
    assert s.singleNonDuplicate([1, 1, 2, 2, 3]) == 3

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Single in the middle | Checks normal parity shift |
| Single near the end | Checks right-side search |
| One element | Minimum input |
| Single at the beginning | Checks left boundary |
| Single at the end | Checks right boundary |