class Solution {
public:
bool isRightOdd(vector<int>& nums, int mid) {
int k = -1;
for(int j = mid -1; j < nums.size(); j++) {
if(mid != j && nums[mid] == nums[j]) {
k = j;
break;
}
}
if(k == -1) {
return true;
}
int minidx = min(mid, k);
if((nums.size() - minidx)%2 == 0) {
return false;
}
return true;
}

int singleNonDuplicate(vector<int>& nums) {
int lo = 0;
int hi = nums.size();
while(lo + 1 != hi) {
int mid = (lo + hi) /2;
if(isRightOdd(nums, mid)) {
lo = mid;
}
else {
hi = mid;
}
}
return nums[lo];
}
};


이분탐색 이진탐색