[C++] O(log n) time O(1) space | Simple and clean | Use xor to keep track of odd even pair
nums[mid] == nums[mid ^ 1] for odd position compares with the previous number; for even position compares with the next number. The unique number must be at eve
**nums[mid] == nums[mid ^ 1]** for odd position compares with the previous number; for even position compares with the next number. The unique number must be at even position.\n \n```\nint singleNonDuplicate(vector<int>& nums) {\n\tint start=0, end = nums.size()-1, mid;\n\twhile( start < end ) {\n\t\tmid = start + (end-start)/2;\n\t\tif( nums[mid] == nums[mid ^ 1] )\n\t\t\tstart = mid + 1;\n\t\telse\n\t\t\tend = mid;\n\t}\n\treturn nums[start];\n}\n```\n\nIn case above one looks more complicated to you:\n\n```\nint singleNonDuplicate(vector<int>& nums) {\n\tint left = 0, right = nums.size() - 1;\n\twhile(left < right){\n\t\tint mid = (left + right)/2;\n\t\tif((mid % 2 == 0 && nums[mid] == nums[mid + 1]) || (mid % 2 == 1 && nums[mid] == nums[mid - 1]))\n\t\t\tleft = mid + 1;\n\t\telse\n\t\t\tright = mid;\n\t}\n\treturn nums[left];\n}\n```
[]