###### tags: `Leetcode` `medium` `binary search` `python` `c++`

# 540. Single Element in a Sorted Array

## [題目連結:] https://leetcode.com/problems/single-element-in-a-sorted-array/description/

## 題目:
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in ```O(log n)``` time and ```O(1)``` space.

**Example 1:**

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

**Example 2:**

Input: nums = [3,3,7,7,10,11,11]
Output: 10

## 解題想法:
* 此題為給一排序好的數組，其中僅有一數恰出現一次
* time: O(logN)
* space: O(1)

* 懶人大法:
* 直接全部xor即可
* 但time: O(n)

* 看到O(logN): 往二分法思考
* 找到位置Mid，判斷是否與左右值相同
* 初始:
* head=0
* tail=len(nums)-1
* while 判斷: head **<** tail:
* 不需要等於，因為若等於，判斷mid時會out of range
* case1: 若當前位置的值與左右皆不同
* mid=(head+tail)/2
* if (nums[mid]!=nums[mid-1] and nums[mid]!=nums[mid+1]): return nums[mid]
* 上述這樣寫並不嚴謹，對於c++而言，因為對於邊界mid=0 or mid=nums.size()-1時候，無法得知mid-1與mid+1，會out of range
* case2: **技巧判斷**
* **判斷當前mid所在位置為奇數or偶數**
* 若為偶數:
* 因為起始位置從0開始，若mid為偶數，**表示mid左邊恰好為偶數個數字，且兩兩成對**，則若同時**nums[mid]與其右邊nums[mid+1]相等**，表示左半邊皆合格，可以將head=mid+1
* 若為奇數:
* 因為起始位置從0開始，若mid為奇數，**表示mid左邊有奇數個數字，可以視為兩兩成對+額外多一個(nums[mid-1])**，則若同時**nums[mid]與其左邊nums[mid-1]相等**，表示左半邊皆為兩兩成對合格，可以將head=mid+1
* case3:
* 反之為tail=mid-1

## Python:

class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #O(n):直接全部xor即可
        #O(logN):二分法
        #找到Mid 判斷是否與左右相同
        head=0
        tail=len(nums)-1
        while head<tail: #不能等於 因為怕底下判斷mid會out of range
            mid=(head+tail)//2
            if nums[mid]!=nums[mid-1] and nums[mid]!=nums[mid+1]:
                return nums[mid]
            #若mid在偶數位置且nums[mid]與其右邊nums[mid+1]相等
            #若mid在奇數位至且nums[mid]與其左邊nums[mid-1]相等
            #代表mid左邊數全部都兩兩成對
            if (mid%2==0 and nums[mid]==nums[mid+1])or(mid%2==1 and nums[mid]==nums[mid-1]):
                head=mid+1
            else: #否則mid右邊數全部都兩兩成對
                tail=mid-1
        return nums[head]

nums = [3,3,7,7,10,11,11]
result= Solution()
ans=result.singleNonDuplicate(nums)
print(ans)

## C++:

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n=nums.size(), head=0, tail=n-1;
        while (head<tail){
            int mid=head+(tail-head)/2;
            if (mid>0 && mid<n-1){
                if ((nums[mid]!=nums[mid-1]) && (nums[mid]!=nums[mid+1]))
                    return nums[mid];
            }
            if ((mid%2==0 && nums[mid]==nums[mid+1]) || (mid%2==1 && nums[mid]==nums[mid-1]))
                head=mid+1;
            else
                tail=mid-1;
        }
        return nums[head];
    }
};