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
Newbie Developer

Newbie Developer

More from Medium

Speech simple and complex

CS373 Spring 2022: Mara Manskie

WHAT IS CODING?

How do you start