540. Single Element in a Sorted Array

Description:

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

 

 

'''
[1] binary search)

idea::
set left and right.
compare mid with both mid-1 and mid+1

code::
    def singleNonDuplicate(self, nums: List[int]) -> int:
        # exception
        if len(nums)==1:
            return nums[0]
        
        l,r=0,len(nums)-1
        while r-l+1>=3:
            mid=(l+r)//2
            
            if r-l+1==3:
                if nums[mid]!=nums[mid+1]:
                    return nums[r]
                else:
                    return nums[l]
            if (r-mid)%2==0:
                if nums[mid]==nums[mid-1]:
                    r=mid
                elif nums[mid]==nums[mid+1]:
                    l=mid
                else:
                    return nums[mid]
            else:
                if nums[mid]==nums[mid-1]:
                    l=mid
                elif nums[mid]==nums[mid+1]:
                    r=mid-1
                else:
                    return nums[mid]
        
-T/C: O(logn)
-S/C: O(1)
'''

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        # exception
        if len(nums)==1:
            return nums[0]
        
        l,r=0,len(nums)-1
        while r-l+1>=3:
            mid=(l+r)//2
            
            if r-l+1==3:
                if nums[mid]!=nums[mid+1]:
                    return nums[r]
                else:
                    return nums[l]
            if (r-mid)%2==0:
                if nums[mid]==nums[mid-1]:
                    r=mid
                elif nums[mid]==nums[mid+1]:
                    l=mid
                else:
                    return nums[mid]
            else:
                if nums[mid]==nums[mid-1]:
                    l=mid
                elif nums[mid]==nums[mid+1]:
                    r=mid-1
                else:
                    return nums[mid]