leetcode 540 single element in a sorted array

我的参考代码（C++）：

https://github.com/liuyubobobo/Play-Leetcode/blob/master/0501-1000/0540-Single-Element-in-a-Sorted-Array/cpp-0540/main.cpp

整体思路：

nums 最后补一个 -1，这样，整个数组一定有 2n 个数字，n 个不同的数字。

在数组开始的时候，每两个数字都是成对出现的，所以 2 * i 和 2 * i + 1 位置的数字应该是一样的；

直到出现了一个数字不是成对出现的，从这个数字往后，2 * i 和 2 * i + 1 的位置的数字就不一样了；

因为整个数组是有序的，我们可以二分搜索，找到这个 2 * i 和 2 * i + 1 的数字不一样的最早位置。

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        
        nums.push_back(-1); // 补 -1，让整个数字的元素个数为偶数，这样不会出现数组越界
                            // 之所以补 -1 是因为数组元素 >= 0，所以 -1 不会和任何元素重复，是安全的
        int n = nums.size() / 2;
        int l = 0, r = n - 1;
        while(l < r){
            int mid = (l + r) / 2;
            if(nums[2 * mid] != nums[2 * mid + 1]) // 如果 2 * mid 和 2 * mid + 1 的元素不等
                r = mid; // 看看有没有更早的不等的位置
            else
                l = mid + 1; // 如果相等，肯定不是解
        }
        return nums[2 * l];
    }
};

继续加油！：）