Given a sorted array consisting of only integers where every element appears twice except for one element which appears 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.

Difficulty: interview

Starter code:

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def singleNonDuplicate(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         return self.singleNonDuplicateUtil(nums, 0, len(nums)-1)
         
     def singleNonDuplicateUtil(self, nums, l, r):
         if l < r:
             mid = int((l + r) * 0.5)
 
             if mid-1>=0 and nums[mid-1]!=nums[mid]:
                 mid=mid-1
 
             if (mid - l + 1) % 2 == 0:
                 l = mid + 1
             else:
                 r = mid
 
 
             return self.singleNonDuplicateUtil(nums, l, r)
         else:
             return nums[l]

class Solution:
     def singleNonDuplicate(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         res = 0
         for i in nums:
             res ^= i
         return res


class Solution:
     def singleNonDuplicate(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         count = len(nums)
         lo = 0
         hi = int(count/2)
         while lo < hi:
             m = int((lo + hi)/2)
             if nums[2*m] != nums[2*m+1]:
                 hi = m
             else:
                 lo = m + 1
         return nums[2*lo]


class Solution:
     def singleNonDuplicate(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         i, j = 0, len(nums)-1
         while i < j:
             mid = i + (j - i) // 2
             if mid % 2 == 1:
                 mid -= 1
             if nums[mid] == nums[mid + 1]:
                 i = mid + 2
             else:
                 j = mid
         return nums[i]

class Solution:
     def singleNonDuplicate(self, nums):
         if len(nums)==1:
             return nums[0]
         flag=0
         for i in range(len(nums)):
             if flag==0:
                 if i==len(nums)-1:
                     return nums[i]
                 if nums[i]==nums[i+1]:
                     flag=1
                 else:
                     return nums[i]
             else:
                 flag=0
                 continue

class Solution:
     def singleNonDuplicate(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         # # O(N) time complexity O(1) space using bit XOR manipulation
         # x = nums[0]
         # for num in nums[1:]:
         #     x = x^num
         # return x
         
         
         # O(logN) runtime and O(1) Space using cool binary search (it's sorted)
         # focuses on the index
         
         left = 0
         if len(nums) == 1:
             return nums[left]
         
         right = len(nums) - 1
         
         while left < right:
             mid = left + (right - left) // 2
             
             if mid % 2 == 1:
                 mid -= 1
             
             if nums[mid + 1] == nums[mid]:
                 left = mid + 2
             
             else:
                 right = mid
         
         return nums[left]
         
         
         
         
         
         
         
         
         
         


class Solution:
     def singleNonDuplicate(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         #return sum(set(nums))*2-sum(nums)
         '''
         one = 0
         for num in nums:
             one = (~one&num)|(one&~num)
         return one
         '''
         l, r = 0, len(nums)-1
         while l < r:
             mid = (l+r)//2
             if nums[mid] == nums[mid-1]:
                 if (r-mid)%2 == 1:
                     l = mid + 1
                 else:
                     r = mid - 2
             elif nums[mid] == nums[mid+1]:
                 if (mid-l)%2 == 1:
                     r = mid - 1
                 else:
                     l = mid + 2
             else:
                 return nums[mid]
         return nums[l]


class Solution:
     def singleNonDuplicate(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         while nums:
             if len(nums)>1 and nums[0]==nums[1] :
                 nums.pop(0)
                 nums.pop(0)
             else:
                 return nums[0]

class Solution:
     def singleNonDuplicate(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         while nums:
             if len(nums)>1 and nums[0]==nums[1] :
                 nums.pop(0)
                 nums.pop(0)
             else:
                 return nums[0]
             


class Solution:
     def singleNonDuplicate(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         return 2*sum(set(nums))-sum(nums) #arrays don't usually present themselves sorted for binary search in real life


class Solution:
     def singleNonDuplicate(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if len(nums) == 1:
             return nums[0]
         startIndex = 0
         endIndex = len(nums) - 1 
         while startIndex < endIndex:
             midIndex = (endIndex - startIndex)//2 + startIndex
             midValue = nums[midIndex]
             leftValue = nums[midIndex - 1] if midIndex - 1 >= 0 else None
             rightValue = nums[midIndex + 1] if midIndex + 1 < len(nums) else None
             
             numLeftUnknowns = midIndex
             numRightUnknowns = len(nums) - 1 - midIndex
             if (leftValue != midValue and rightValue != midValue):
                 return midValue
             elif leftValue == midValue:
                 numLeftUnknowns -= 1
             else:
                 numRightUnknowns -= 1
                 
             if numLeftUnknowns % 2 != 0:
                 endIndex = midIndex - 1
             else:
                 startIndex = midIndex + 1
             
         return nums[startIndex]