540. 有序数组中的单一元素

思路

二分查找

根据数组有序可以知道，如果前面没有插入单个的元素

那么偶数位置上面的数字应该等于偶数位置+1的数

奇数位置的数等于奇数位置减一位置上的数

如果不相等那么就说明前面插入了单个的元素，更新r

Solutions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
       int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (mid % 2 == 0) {
                if (mid + 1 < n && nums[mid] == nums[mid + 1]) l = mid + 1;
                else r = mid;
            } else {
                if (mid - 1 >= 0 && nums[mid - 1] == nums[mid]) l = mid + 1;
                else r = mid;
            }
        }
        return nums[r];
    }
};