```
int singleNonDuplicate(vector<int>& nums) {
if (nums.empty()) return 0;
int begin = 0, end = nums.size() - 1;
while (begin != end) {
int mid = (begin + ((end - begin)>>1))&~1; // make sure mid falls on even position
nums[mid] == nums[mid + 1] ? begin = mid + 2 : end = mid;
}
return nums[begin];
}
```