Easy Binary Search Explanation | O(logn) | O(1)
Intuition\nLet\'s look at an example array [3,3,4,4,5,6,6,7,7]. We look at indicies 0, 2, 4, 6, 8 and check if the number is equal to the number on its right.\n
# Intuition\nLet\'s look at an example array `[3,3,4,4,5,6,6,7,7]`. We look at indicies `0, 2, 4, 6, 8` and check if the number is equal to the number on its right.\n```\n  index:  0  1  2  3  4  5  6  7  8\n   nums:  3  3  4  4  5  6  6  7  7\nmatches:  T     T     F     F     F\n```\nAt the singleton number, the numbers stop matching with the number to its right. We can do binary serach to find this position where the numbers stop matching.\n\n# Complexity\n- Time complexity: Binary search on an array of size `n` takes O(logn).\n\n- Space complexity: Constant space is needed for binary search, so O(1).\n\n# Code\n```\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        l, r = 0, len(nums) // 2\n        ans = -1\n        while l <= r:\n            mid = (l + r) // 2\n            idx = mid * 2\n            if idx + 1 >= len(nums) or nums[idx] != nums[idx + 1]:\n                r = mid - 1\n                ans = nums[idx]\n            else:\n                l = mid + 1\n        return ans\n```
['Python3']