题目描述

找出数组中只出现一次的元素，要求用logn的时间。

本题在二分模板2基础上，只搜索满足条件的偶数位置。

对于合法的序列，例如 11 33 44， 可以发现偶数下标i对应的数nums[i] 等于nums[i + 1]

而不合法序列 如 11 22 3 44 可以发现出现3之后的偶数位置不满足了nums[i] 等于nums[i + 1]这个性质

那么用模板2搜索满足nums[i] != nums[i + 1]的最小下标，可以发现此时的结果就是单个元素的位置。

有一点要注意，就是要保证mid也是偶数，如果是奇数就-1。因为要保证位置最小，所以不能用++。

C++ 代码

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0;
        int r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (mid % 2 == 1) mid --;
            if (nums[mid] != nums[mid + 1]) r = mid;
            else l = mid + 2;

        }
        return nums[l];


    }
};