Description

Submission

class Solution {
    int n;
    bool checkOK(int idx, vector<int>& nums) {
        if(idx % 2 == 1) {
            if(nums[idx-1] == nums[idx]) return true;
        } else {
            if(idx + 1 < n && nums[idx+1] == nums[idx]) return true;
        }

        return false;
    }
public:
    int singleNonDuplicate(vector<int>& nums) {
        n = nums.size();

        int left = 0, right = n - 1;

        while(left < right) {
            int mid = left + (right - left) / 2;

            if(checkOK(mid, nums)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
};


// 0 1 2 3 4 5 6 7
// 1 1 2 3 4 4 8 8