题目

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

在这里插入图片描述

解题思路

这个题可以用二分法来做。值得注意的是要考虑四种情况，且题目有时间复杂度和空间复杂度的要求。

情况1：中间元素的同一元素在右边，且目标元素在右边

情况2：中间元素的同一元素在右边，且目标元素在左边

情况3：中间元素的同一元素在左边，且目标元素在左边
情况4：中间元素的同一元素在左边，且目标元素在右边

注意的点：
①进行判断目标元素的在左边还是右边的核心思想是，除去了mid的相同元素，数组个数是偶数，则没有目标元素，反之，有目标元素

②本来按常人思维，mid同一元素在右边就去判断右边的数组，在左边就去判断左边的数组，但是因为题目的时间复杂度要求，我们统一判断右边的数组个数。用(right \- mid) % 2 == 0。

③本来判断是否存在目标元素是根据“除去了mid的相同元素，再看右边数组个数”，但是具体不好实现，所以分两种情况。
1）、中间元素的同一元素在右边：此时(right \- mid) % 2 == 0，证明目标元素存在右边
2）、中间元素的同一元素在左边：此时(right \- mid) % 2 ！= 0，证明目标元素在右边

④注意mid和flag的定义都要放到while循环里面，不然会超时

代码

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
    

        while (left < right) {
                int mid = left + (right - left) / 2;//其实mid就等于(l+r)/2，这里这么写是为了防止溢出
            boolean flag = (right - mid) % 2 == 0;
            if (nums[mid] == nums[mid + 1]) {
                if (flag) {//①mid相同元素在mid右边，且去除该相同元素后，右边数组为奇数。即目标值在右边部分
                    left = mid + 2;
                } else {//②mid相同元素在mid右边，且去除该相同元素后，右边数组为偶数。即目标值在左边部分
                    right = mid - 1;
                }

            } else if (nums[mid] == nums[mid - 1]) {
                if (flag) {//③mid相同元素在mid左边，且去除该相同元素后，左边数组为奇数。即目标值在左边部分
                    /*本来if的条件应该是(mid - left) % 2 != 0，但是由于这样会导致超时，所以我们只用一个变量，flag。
                      即flag为true的时候证明右子块没有目标元素  */
                    right = mid - 2;
                } else {//④mid相同元素在mid左边，且去除该相同元素后，左边数组为偶数。即目标值在右边部分
                    left = mid + 1;
                }

            } else {//如果上面条件都不满足，证明中间的元素就是目标元素
                return nums[mid];
            }

        }
        return nums[left];//这是为了防止数组只有一个元素，那么就直接返回该元素，nums[0]
    }
}