有序数组中的单一元素(Single Element in a Sorted Array)

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

示例 1:

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

示例 2:

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

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

int singleNonDuplicate(int* nums, int numsSize){
    int ans = nums[0];
    for (int i = 1; i < numsSize; ++i) {
        ans ^= nums[i];
    }
    return ans;
}

这个做法和之前的做法是一模一样的，这边应该有更妙的做法，毕竟条件更多了

int singleNonDuplicate(int* nums, int numsSize){
    for (int i = 0; i+1 < numsSize; i+=2) {
        if (nums[i] != nums[i+1]){
            return nums[i];
        }
    }
    return nums[numsSize-1];
}

这样的做法也是比较简单的，而且不用用到异或，更清楚，但是时间复杂度还是O(n)

int binarySearch(int* nums, int begin, int end){
    if (end - begin == 1) return  nums[begin];
    int mid = begin + (end - begin)/2;

    if (nums[mid-1] < nums[mid] && nums[mid] < nums[mid+1]) return nums[mid];
    if (mid % 2 == 0 && nums[mid-1] < nums[mid] && nums[mid] == nums[mid+1]) return binarySearch(nums, begin, mid);
    if (mid % 2 == 0 && nums[mid-1] == nums[mid] && nums[mid] < nums[mid+1]) return binarySearch(nums, begin, mid-1);
    if (mid % 2 == 0 && nums[mid-1] < nums[mid] && nums[mid] == nums[mid+1]) return binarySearch(nums, mid+2,end);
    if (mid % 2 == 1 && nums[mid-1] == nums[mid] && nums[mid] < nums[mid+1]) return binarySearch(nums, mid, end);
    return -1;
}


int singleNonDuplicate(int* nums, int numsSize){
    for (int i = 0; i+1 < numsSize; i+=2) {
        if (nums[i] != nums[i+1]){
            return nums[i];
        }
    }
    return nums[numsSize-1];
}

排序自然会想到二分法呀，然后就可以让时间复杂度变成 O(log n)了，并且我们看到 binarySearch 只会在return 的时候才调用自己，因此是一个伪递归，因此可以转化为while循环.