题目

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

题目链接：有序数组中的单一元素

示例

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

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

题解

今天的每日一题，今天情人节，情人节可不兴用二分（手动狗头）。这题很久之前刷过，用位运算，代码很简洁，能过，但O(n)复杂度不满足题目要求。

题目读到一半，首先想到的是map映射，返回value为1的key，但题目给出了时间复杂度和空间复杂度要求，题目又给出“有序数组”的条件，果断二分，但怎么判断该往哪一部分搜索呢？仔细想想也不难，只有一个孤独的数字，那么判断一下数组左右两边元素个数就可以了。

代码实现

class Solution {
    public int search(int[] nums, int low, int high) {
        if(low < high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] == nums[mid-1]) { // 中点跟左边的相等，则判断左边
                if((mid-low) % 2 == 0) return search(nums, low, mid-2); // 为偶数，说明左边存在答案
                else return search(nums, mid+1, high); // 为奇数，说明右边存在答案
            } else if(nums[mid] == nums[mid+1]) { // 中点跟右边的相等，则判断右边
                if((high-mid) % 2 == 0) return search(nums, mid+2, high); // 为偶数，说明右边存在答案
                else return search(nums, low, mid-1); // 为奇数，说明左边存在答案
            } else { // 中点左右不等，即为答案
                return nums[mid];
            }
        }
        return nums[high];
    }

    public int singleNonDuplicate(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }
}