# Leetcode 540 - Single Element in a Sorted Array ### Understanding the problem

The problem statement on LeetCode reads as follows:

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.

Follow up: Your solution should 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

One way to solve this problem is to use a binary search algorithm. Since the array is sorted, we can take advantage of this property to find the single element that appears only once in O(log n) time.

We can start by setting the left and right pointers to the first and last elements in the array, respectively. Then, we can check if the middle element is equal to its left or right neighbor. If it is equal to its left neighbor, it means that the single element is on the right side of the array, so we can move the left pointer to the middle point between the left and right pointers. On the other hand, if it is equal to its right neighbor, it means that the single element is on the left side of the array, so we can move the right pointer to the middle point. We can repeat this process until the left and right pointers meet. This will give us the single element that appears only once.

Now that we have a plan, let’s implement it in Python.

``````class Solution:
def singleNonDuplicate(self,nums):
# Set the left and right pointers to the first and last elements in the array
left, right = 0, len(nums) - 1

# While the left pointer is less than the right pointer
while left < right:
# Calculate the middle point between the left and right pointers
mid = (left + right) // 2

# Check if the middle element is equal to its left or right neighbor
if nums[mid] == nums[mid - 1]:
# If it is equal to its left neighbor, it means that the single element is on the right side of the array
left = mid + 1
elif nums[mid] == nums[mid + 1]:
# If it is equal to its right neighbor, it means that the single element is on the left side of the array
right = mid - 1
else:
# If it is not equal to either its left or right neighbor, it means that the middle element is the single element
return nums[mid]

# Return the left pointer (which is the single element)
return nums[left]
``````