[Python] short binary search, explained
Straightforward way is to just iterate over all elements in O(n). There is smarter binary search solution. For example we have aa bb cc dd ee ff gg h ii jj kk. 
Straightforward way is to just iterate over all elements in `O(n)`. There is smarter binary search solution. For example we have `aa bb cc dd ee ff gg h ii jj kk`. Let us find middle element, but shift it by one if number of element in the left part is odd: we always consider even number of elements in the left part. Then if `nums[mid] == nums[mid-1]` it means, that in the left part all elements are paired and we need to look in the right part. In the opposite case it means, that we need to look into the left half.\n\n#### Complexity\nTime complexity is `O(log n)`, space complexity is `O(1)`.\n\n#### Code\n```python\nclass Solution:\n    def singleNonDuplicate(self, nums):\n        beg, end = 0, len(nums) - 1\n\n        while end > beg + 1:\n            mid = (beg + end)//2\n            if (mid - beg) % 2 == 0: mid += 1  \n            if nums[mid] == nums[mid - 1]: \n                beg = mid + 1\n            else:\n                end = mid \n\n        return nums[beg]\n```\n\nIf you have any questoins, feel free to ask. If you like the solution and explanation, please **upvote!**
['Binary Search']