< Back





540. Single Element in a Sorted Array

We're given a list of integers where one integer is unique, the rest appear exactly twice. We use
this nature to understand that the unique integer we're looking for will always be at an even index.
We can use binary search to find the unique integer. We compare the middle element with the element
to its right. If they're equal, we know the unique integer is in the right half. If they're not
equal, we know the unique integer is in the left half. We continue this process until we find the
unique integer.

The solution is as follows:


  class Solution:
      def singleNonDuplicate(self, nums: List[int]) -> int:
          l, r = 0, len(nums) - 1

          while l < r:
              m = (r + l) // 2

              if m % 2 == 1:
                  m -= 1

              if nums[m] == nums[m + 1]:
                  l = m + 2
              else:
                  r = m

          return nums[l]


_ Time Complexity:

  O(log(n)) - Where n is the length of the array.

_ Space Complexity:

  O(1) - Binary search requires constant space.