题目

• 给定一个只由数字组成的有序数组，除了其中一个元素只出现一次别的都会出现两次，找出只出现一次的那个元素。
• 比如输入[1,1,2,3,3,4,4,8,8]，输出2
• 输入[3,3,7,7,10,11,11],输出10

解题思路

• 这道题常规做法可以参考之前的single number用异或操作即可获得结果，但是时间复杂度为O(n)与题目要求O(logn)不符合
• 根据log(n)的要求可以猜测使用二分查找，此时我们需要辨别一下规律，题意中给出的数组是有序的如果按照常规的两两出现比如[0,0,1,1],此时的下标对应的应该是 0,1,2,3。也即是重复的数字下标是偶奇偶奇的组合（从0开始），但是如果中间多了一个单次的数字比如3，此时数组变为[0,0,3,1,1]那么此时下标0,1,2,3,4后面两个数字1,1表示的数字就变成了3,4（下标奇偶特性）。
• 由以上所述我们可以二分查找首先确定mid的奇偶性，然后再判断相等的两个数连续的奇偶性，举例来说当mid%2==0时，此时表示mid是偶数下标，那么如果按照原始两两排列应该是偶奇特性，此时就用nums[mid]和nums[mid+1]比较，如果相等那么表示mid之前的序列都是两两出现的，并没有破坏平衡性，此时low更新为mid，相反的就是mid和mid-1相等，或者mid是单独的数字，直接将high更新为mid。同理可以更改mid为奇数下标时的情况。
• 采用二分查找整体时间复杂度为O(logn)

源代码实现

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int low = 0, high = nums.length-1;
        while (low < high) {
            int mid = low + (high - low)/2;
            //前后都不等那么nums[mid]就是要查找的数据
            if (nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]) return nums[mid];
            //mid表示偶数位置（从0开始）
            if (mid % 2 == 0) {
                if (nums[mid] == nums[mid+1]) low = mid;
                else high = mid;
            }
            else {
                if (nums[mid] == nums[mid-1]) low = mid+1;
                else high = mid-1;
            }
        }
        return nums[low];
    }
}