Python | Binary Search | O(logn) time & O(1) space | Simple Solution With Explanation
Logic\n1. Since we don\'t have any target element to search for so we can\'t directly decide which part of array we need to look for single element.\n2. Since w
# Logic\n1. Since we don\'t have any target element to search for so we can\'t directly decide which part of array we need to look for single element.\n2. Since we know that every element has a duplicate except one so we can commit that the length of array will always be odd.\n3. Now, based on the above logic we can decide which part of array to look for. We can simply check which part of array([start:mid+1] OR [mid+1:end]) has odd number of elements.\n\n**NOTE:** In this solution, I\'m always updating the mid to be on the second index of every duplicate and then I count. You may do the vice-versa also by keeping the mid on first index of every duplicate and update start and end accordingly.\n\n```\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        if len(nums) == 1:\n            return nums[0]\n        start = 0\n        end = len(nums) - 1\n        while start <= end:\n            mid = start + ((end - start) // 2)\n            # Check if mid is the single number\n            if start < mid < end and nums[mid-1] < nums[mid] < nums[mid+1]:\n                return nums[mid]\n            else:\n                # Else goto the second index of nums[mid](duplicate) if already not there.\n                if mid < end and nums[mid] == nums[mid+1]:\n                    mid += 1\n            \n            if (mid - start + 1) % 2:\n                end = mid - 2\n            else:\n                start = mid + 1\n        return nums[start]\n```\n\n***If you liked the above solution then please upvote!***
['Binary Search', 'Binary Tree', 'Python']