30_days_of_data_structure/Maths/singleNonDuplicate540_binary_search.py at main · echobash/30_days_of_data_structure · GitHub

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from typing import List


class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1

        if len(nums) == 1 or nums[0] != nums[1]:
            return nums[0]

        if nums[len(nums) - 1] != nums[len(nums) - 2]:
            return nums[len(nums) - 1]

        while left <= right:
            mid = (left + right) // 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:
                    # Look in right
                    left = mid + 1
                else:
                    right = mid - 1
            elif nums[mid] == nums[mid - 1]:
                if (mid - 1) % 2 == 1:
                    # Look in left
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                return nums[mid]


solution = Solution()
nums = [1,1,2,3,3,4,4,8,8]
print(f"{nums= }{ solution.singleNonDuplicate(nums)= }")

nums = [3,3,7,7,10,11,11]
print(f"{nums= }{ solution.singleNonDuplicate(nums)= }")

nums = [1,1,2,2, 3, 3,4,8,8]
print(f"{nums= }{ solution.singleNonDuplicate(nums)= }")

nums = [1,1,2,2, 3, 4,4,8,8]
print(f"{nums= }{ solution.singleNonDuplicate(nums)= }")