#!/usr/bin/env python
from typing import List
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
start = 0
end = len(nums) - 1
mid = 0
if len(nums) == 1:
return nums[0]
while start < end:
mid = (start + end) // 2
if nums[mid] == nums[mid + 1]:
if (end - mid + 1) % 2 == 0:
end = mid - 1
else:
start = mid
elif nums[mid] == nums[mid - 1]:
if (mid - start + 1) % 2 == 0:
start = mid + 1
else:
end = mid
else:
return nums[mid]
return nums[end]
if __name__ == "__main__":
solution = Solution()
assert solution.singleNonDuplicate([1, 1, 2, 3, 3, 4, 4, 8, 8]) == 2
assert solution.singleNonDuplicate([3, 3, 7, 7, 10, 11, 11]) == 10
assert solution.singleNonDuplicate([1, 2, 2, 3, 3, 4, 4, 8, 8]) == 1
assert solution.singleNonDuplicate([1, 1, 2, 2, 3, 3, 4, 4, 8]) == 8
assert solution.singleNonDuplicate([1, 1, 2]) == 2
assert solution.singleNonDuplicate([0, 1, 1, 2, 2, 5, 5]) == 0
