​LeetCode刷题实战540：有序数组中的单一元素

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: nums = [3,3,7,7,10,11,11]
输出: 10

class Solution {
    public int singleNonDuplicate(int[] nums) {
   int left = 0;
        int right = nums.length - 1;
        while (left < right){
            int mid = left + (right - left) / 2;
            if (nums[mid] == nums[mid + 1]){ // 和u右边相等
                int c = mid - left; //mid左边个数
                if (c%2 == 0){ // 偶数个
                    left = mid + 2;
                }else{
                    right = mid - 1;
                }
            }else if (nums[mid] == nums[mid - 1]){
                int c = right - mid; // mid右边个数
                if (c%2 == 0){ // 偶数个，说明在左边
                    right = mid - 2;
                }else{ // 奇数个，说明在右边
                    left = mid + 1;
                }
            }else{ // 1,1,2,3,3, 不等于右边，也不等于右边，直接返回
                return nums[mid];
            }
        }

        return nums[left];
    }
}