C++ binary search
\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int n = nums.size(), left = 0, right = n - 1;\n        while (left < right
```\nclass Solution {\npublic:\n    int singleNonDuplicate(vector<int>& nums) {\n        int n = nums.size(), left = 0, right = n - 1;\n        while (left < right) {\n            int mid = left + (right - left) / 2;\n            if (mid % 2 == 0) {\n                if (nums[mid] == nums[mid-1]) right = mid - 2;\n                else if (nums[mid] == nums[mid+1]) left = mid + 2;\n                else return nums[mid];\n            }\n            else {\n                if (nums[mid] == nums[mid-1]) left = mid + 1;\n                else if (nums[mid] == nums[mid+1]) right = mid - 1;\n            }\n        }\n        return nums[left];\n    }\n};\n```
[]