LeetCode #540 Single Element in a Sorted Array

Posted on | Post modified | In , , , , , , , , ,

Problem

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Examples

1
2
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
1
2
Input: [3,3,7,7,10,11,11]
Output: 10

Solution

Method: Binary Search (Divide and Conquer)

Time Complexity: O(log n)

Space Complexity: O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 1:
            return nums[0]

        low = 0
        high = len(nums) - 1
        
        while low < high:
            mid = (high + low) // 2
            if nums[mid + 1] != nums[mid] and nums[mid - 1] != nums[mid]:
                return nums[mid]
            if nums[mid] == nums[mid - 1]:
                if mid % 2:
                    low = mid + 1
                else:
                    high = mid - 2
            else:
                if mid % 2:
                    high = mid - 2
                else:
                    low = mid + 1
                    
        return nums[low]