Single Element in a Sorted Array

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
Input: nums = [3,3,7,7,10,11,11]
Output: 10
def singleNonDuplicate(self, nums):
“””
:type nums: List[int]
:rtype: int
“””
if not nums: return None
if len(nums) == 1:
return nums[0]

i, j = 0, len(nums)-1

while i < j:
mid = i + (j-i)/2
if nums[mid] != nums[mid-1] and nums[mid]!=nums[mid+1]:
return nums[mid]
elif nums[mid] == nums[mid+1]:
if mid % 2 == 0:
i = mid + 2
else:
j = mid — 1
else:
if mid % 2 == 0:
j = mid — 2
else:
i = mid + 1

return nums[j]
def singleNonDuplicate(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) / 2
if nums[mid] == nums[mid ^ 1]:
lo = mid + 1
else:
hi = mid
return nums[lo]

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store