Solution to LeetCode 540 Single Element in a Sorted Array.
LeetCode 540
Single Element in a Sorted Array (Medium) [link]
If nums[i] does not equal to nums[i+1], return nums[i], i += 2. This will take time complexity O(n), and space complexity O(1). However, the problem requires time complexity of O(log n).
We resort to Binary Search. Find the first i such that nums[i] != nums[I*], return nums[i]. If i is even, i*=i+1. If i is odd, I*=i-1. Binary search takes time complexity O(log n), space complexity O(1).
class Solution(object):
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = 0
r = len(nums) - 1
while l < r:
m = l + (r - l) // 2
n = m + 1 if m % 2 == 0 else m - 1
if nums[m] == nums[n]:
l = m + 1
else:
r = m
return nums[l]
