Python Binary Search O(logn) - explained
If every element in the sorted array were to appear exactly twice, they would occur in pairs at indices i, i+1 for all even i. \n\nEquivalently, nums[i] = nums[
If every element in the sorted array were to appear exactly twice, they would occur in pairs at indices `i`, `i+1` for all **even** `i`. \n\nEquivalently, `nums[i] = nums[i+1]` and `nums[i+1] != nums[i+2]` for all **even** `i`.\n\nWhen we insert the unique element into this list, the indices of all the pairs following it will be shifted by one, negating the above relationship. \n\nSo, for any **even** index `i`, we can compare `nums[i]` to `nums[i+1]`. \n* If they are equal, the unique element must occur somewhere **after** index `i+1`\n* If they aren\'t equal, the unique element must occur somewhere **before** index `i+1`\n\nUsing this knowledge, we can use binary search to find the unique element.\n\nWe just have to make sure that our pivot index is always even, so we can use `mid = 2 * ((lo + hi) // 4)` instead of the usual `mid = (lo + hi) // 2`.\n<hr>\n\n**Solution:**\n\nTime: `O(logn)`\nSpace: `O(1)`\n\n```\ndef singleNonDuplicate(self, nums: List[int]) -> int:\n\tlo, hi = 0, len(nums) - 1\n\twhile lo < hi:\n\t\tmid = 2 * ((lo + hi) // 4)\n\t\tif nums[mid] == nums[mid+1]:\n\t\t\tlo = mid+2\n\t\telse:\n\t\t\thi = mid\n\treturn nums[lo]\n```
['Binary Search', 'Python']