给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:

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

示例 2:

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

提示:

• 1 <= nums.length <= 10e5
• 0 <= nums[i] <= 10e5

 分析：根据题目要求，首先想到二分。对于当前的位置mid，如果它不是唯一出现的数，那么它的左边或者右边去掉和它相等的数字之后，一定有一边只有奇数个数字，此时进入这一边再次二分。边界条件为数组大小为1，或者mid仅出现过一次。

int getans(int *arr,int n,int l,int r)
{if(r==l)return arr[l];int mid=(l+r)/2;if(mid-1>=0&&mid+1<n){int temp=arr[mid];if(arr[mid-1]==temp||arr[mid+1]==temp){if(arr[mid-1]==temp){if((mid+1-2)%2==1)return getans(arr,n,l,mid-2);else return getans(arr,n,mid+1,r);}else{if((mid)%2==1)return getans(arr,n,l,mid-1);else return getans(arr,n,mid+2,r);}}}return arr[mid];
}int singleNonDuplicate(int* nums, int numsSize) {return getans(nums,numsSize,0,numsSize-1);
}