【奇偶性】个人练习-Leetcode-540. Single Element in a Sorted Array

题目链接：https://leetcode.cn/problems/single-element-in-a-sorted-array/

题目大意：给出一个排好序的数组nums[]，其中所有数字都出现两次，仅有一个数字出现一次。找出这个仅出现一次的数字。要求时间复杂度$O(logN)$，空间复杂度$O(1)$

思路：单纯的遍历当然可以，但时间复杂度是$O(N)$，想要$O(logN)$只能二分。可是该怎么二分？有点难到了，看了hint发现是个脑筋急转弯，利用下标的奇偶性做即可。假设第i个元素是仅出现一次的，那么其必然是偶数，因为先前的数都是成对出现的，下标为【偶、奇】；而在它之后的数对的下标则是【奇、偶】。奇偶性用even和odd表示

下标		0 1 2 3 ... i i+1 i+2
奇偶性 	e o e o ... e  o   e   
数字		x x y y     z  m   m

因此只需要二分查找，找到这个使得奇偶性变化的点即可。

完整代码

class Solution {
public:int singleNonDuplicate(vector<int>& nums) {int l = 0, r = nums.size()-1;int mid;while (1) {if (l == r) {mid = l;break;}mid = (l+r) / 2;if (mid % 2) {// oddif (nums[mid-1] != nums[mid]) {r = mid-1;continue;}else {l = mid+1;continue;}}else {// evenif (nums[mid] != nums[mid+1]) {r = mid;continue;}else {l = mid+2;continue;}}}return nums[mid];}
};