※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 540. Single Element in a Sorted Array
: 給你一個已排序整數陣列，裡面的所有數字都有恰好兩個，只有一個數字只有一個，
: 找出這個數字是什麼，限制時間複雜度：O(logn)且空間複雜度：O(1)。
: Example :
: Input: nums = [1,1,2,3,3,4,4,8,8]
: Output: 2
: Input: nums = [3,3,7,7,10,11,11]
: Output: 10
解題思路:
一樣用 binary search 維護左右邊界，
左邊界 l: 保證不是答案的最大值，初始為 -1，
右邊界 r: 可能是答案的最小值，初始為 size - 1。
由於 l 左邊保證不是答案，所以一定是偶數個數字，
戳到 mid 如果是奇數index (含自己左邊有偶數個數字)，只要跟左邊相鄰數字檢查，
戳到 mid 如果是偶數index (不含自己左邊有偶數個數字)，只要跟右邊相鄰數字檢查，
等到邊界 l + 1 == r 的時候 nums[r] 就是答案。
C++ code:
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int l = -1, r = nums.size() - 1;
while(l + 1 < r){
int mid = (l + r) / 2;
if(mid & 1){
if(nums[mid] == nums[mid - 1]) l = mid;
else r = mid;
}
else{
if(nums[mid] == nums[mid + 1]) l = mid + 1;
else r = mid;
}
}
return nums[r];
}
};