For any Algorithm question, whenever you see a keyword **Sorted** think of *Binary Search*

In the given problem, there is one unique element and rest of all the elements are paired, also the elements are in sorted array

Let's consider this example, with start and end index pointing to first and last element of the array

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

Now the *mid* is 3

if you analyze the diagram

- nums[mid] == nums[mid - 1]

Now there are two cases

- Either the element lies from start to mid
- Or the element lies from mid to end

You can say the element lies in a part where the length is not even

So the conditions will be

- if mid to end is even then the element lies from start to mid, so
`end = mid - 2`

. Why`mid - 2`

because we don't want to iterate`nums[mid]`

and`nums[mid - 1]`

again - if mid to end is odd then the element lies from mid to end, so
`start = mid + 1`

Now Let's consider a case where `nums[mid] == nums[mid + 1]`

The conditions for this scenario is

- if start to mid is even, then element lies from mid to end, so
`start = mid + 2`

- else
`end = mid - 1`

Now there comes a scenario where nums[mid] is not equal to nums[mid + 1] or nums[mid -1], that's the element we have to return

Here is the code

```
var singleNonDuplicate = function(nums) {
let start = 0, end = nums.length - 1
while(start <= end) {
let mid = Math.floor((start + end) / 2)
if(nums[mid] == nums[mid - 1]) {
let isEven = (end - mid) % 2 == 0
if(isEven) {
end = mid - 2
} else {
start = mid + 1
}
} else if(nums[mid] == nums[mid + 1]) {
let isEven = (mid -start) % 2 == 0
if(isEven) {
start = mid + 2
} else {
end = mid - 1
}
} else {
return nums[mid]
}
}
};
```

## Top comments (0)