leetcode 540. Single Element in a Sorted Array（排序数组中的单个元素）

给一个已经排好序的升序数组，其中每个元素都会重复2次，只有一个元素只有一个，
找出这个只有一个的元素。
要求时间复杂度在O(logn), 空间复杂度在O(1).

思路：

时间复杂度为O(logn), 让人想到了binary search.

因为时间复杂度为O(1), 所以不能用一个数组来保存每个元素出现的次数。

不过，每个元素也就出现2次，而且是排好序的，也就是说相同的元素都是在一起的。
可以用一个cnt, 元素第一次出现时cnt = 1, 第2次出现时cnt = 0,
那么只出现一次的元素，cnt就无法清0，于是就被找出来了。
但是这种方法需要遍历数组，时间复杂度为O(n), 也能通过测试。

publicintsingleNonDuplicate(int[] nums){int cnt =1;int n = nums.length;if(n ==1)return nums[0];for(int i =1; i < n; i++){if(nums[i]!= nums[i-1]){if(cnt ==1)return nums[i-1];else cnt =1;}else{
                cnt =0;}}return nums[n-1];}

下面看一下binary search.

为什么能用binary search呢？
因为每个元素出现2次（长度为偶数），只有一个元素出现了1次，
包含出现了1次的元素的部分，长度一定是奇数。

我们可以判断奇数的长度出现在左边还是右边，把left, right指针卡在奇数长度的部分。

举个例子：
2，2，3，3，4
[0] [1] [2] [3] [4]
left = 0, right = 4, mid = 2
右半边的长度（不含mid本身）为right - mid = 2, 长度为偶数，

但是发现没有，nums[mid]和nums[mid+1]两个数是一样的，
现在的长度right-mid 把两个相同的元素拆开了，违背了刚才判断的标准，
2个相同的元素都在一起才符合长度为偶数的标准，拆开了就不能按照长度为奇偶来判断了。

所以要比较nums[mid]和nums[mid+1]两个元素，如果相同，把nums[mid]也算进右边，
所以现在右边长度为奇数，可以判断单个的元素在右边，移动left = mid + 2（跳过重复元素）。
那如果是下面的例子：
1，2，2，3，3,
可以看到右边长度为偶数，这时要移动right = mid - 2（跳过重复元素）

直到nums[mid] 和 nums[mid + 1], nums[mid-1]都不相等, 返回nums[mid].

publicintsingleNonDuplicate(int[] nums){int n = nums.length;if(n ==1)return nums[0];int left =0;int right = n -1;while(left <= right){int mid = left +(right - left)/2;boolean isEvenLen =((right - mid)%2==0);if(mid >=1&& nums[mid]== nums[mid-1]){if(isEvenLen) right = mid-2;else left = mid +1;//重复元素算进右边长度}elseif(mid < n -1&& nums[mid]== nums[mid+1]){if(isEvenLen) left = mid +2;//算进重复元素后，右边长度为奇数，单个元素在右边else right = mid -1;}else{return nums[mid];}}return-1;}