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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

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

Solutions:
class Solution:

	def singleNonDuplicate(self, nums):
		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):
		res = 0
		for i in nums:
			res ^= i
		return res


class Solution:

	def singleNonDuplicate(self, nums):
		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):
		(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):
		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):
		(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):
		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):
		return 2 * sum(set(nums)) - sum(nums)


class Solution:

	def singleNonDuplicate(self, nums):
		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]