LeetCode: Single Element in a Sorted Array
Tags: leetcode, datastructure, algorithms, binarysearch
Published: 2020-05-13 07:28:15

---
title: LeetCode: Single Element in a Sorted Array
published: true
description: 12.05.2020
tags: leetcode, datastructure, algorithms,binarysearch
series: LeetCode May Challenge
---



### Problem Statement

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

 

**Note:** Your solution should run in O(log n) time and O(1) space.



### Solution

```c++
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int L=0, U=nums.size()-1;
        int result;
        while(L<=U)
        {
            if(L==U)
            {
                result = nums[L];
                break;
            }
            int M = L+(U-L)/2;
            int consideredLength = M-L+1;
            if(consideredLength%2 == 1)
            {
                if(M-1>=0 && nums[M] == nums[M-1]) {
                    U = M-2;
                }
                else if(M+1<= nums.size()-1 && nums[M] == nums[M+1]) {
                    L = M+2;
                }
                else {
                    result = nums[M];
                    break;
                }
            }
            else {
                if(M+1<= nums.size()-1 && nums[M] == nums[M+1]) {
                    U = M-1;
                }
                else if(M-1>=0 && nums[M] == nums[M-1]) {
                    L = M+1;
                }
                else {
                    result = nums[M];
                    break;
                }
            }
        }
        return result;
        
    }
};
```



### Solution Thought Process

I solved this problem using binary search. First, we get the middle element of the range using low and high.

We get the length considered by calculating:

```
consideredLength = M-L+1
```

1. Let's consider if this length is odd.

```
nums  1    1    2    2    3
idx   0    1    2    3    4

L = 0, U = 4

M = 0 + (4-0)/2 = 2
```

So`[L, M]` is odd in length. If this is the case, if `nums[M] == nums[M+1]`, it means that the element can be found from element index `M+2`. So we make `L=M+2`

Let's see another case,

```
nums  1    2    2    3    3
idx   0    1    2    3    4

L = 0, U = 4

M = 0 + (4-0)/2 = 2
```

So `[L, M]` is odd in length. If `nums[M] == nums[M-1]` , it means that the element can be found before element index `M-2` , included.

If those are not the case, then `nums[M]` is the result and we break the loop. 

2. Let's consider if the considered length is even.

```
nums  1    1    2    3    3    5    5  
idx   0    1    2    3    4    5    6

L = 0, U = 6

M = 0 + (6-0)/2 = 3
```

So `[L, M]` is even in length. If `nums[M] == nums[M+1]`, it means that the element can be found before element index `M-1`, included . So we make `U = M-1`

```
nums  1    1    2    2    3    5    5  
idx   0    1    2    3    4    5    6

L = 0, U = 6

M = 0 + (6-0)/2 = 3
```

So `[L, M]` is even in length. If `nums[M]==nums[M-1]`, it means that the element can be found from element index `M+1`. So we make `L=M+1`.

If we have got `L` and `U` as the same element, we return the element as the result.



### Complexity

**Time Complexity:** O(logn), we are making the consideration space half in every iteration.

**Space Complexity:** O(1)