# [540. Single Element in a Sorted Array](https://leetcode.com/problems/single-element-in-a-sorted-array/)
###### tag:`medium` `binary search`
contirbuted by <`ctfish7063`>
## 題目
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

## 初解讀和嘗試
因為題目指定了時間複雜度要在$O(log n)$，直覺上我選擇了二元搜尋來進行嘗試。

首先觀察一下輸入，可以發現因為只有一個數字不重複，長度一定會是奇數，可以每次都指定正中間的值當作受害者和他的鄰居比較，分成兩種狀況：
**1. 跟兩旁不同**
他就是那個沒朋友的，像底下這樣

**2. 跟兩旁相同**
可以跨過自己的同伴迭代，像這樣

這時候又可以發現剩下的搜索區長度可能是奇數或偶數，於是可以分成：
1. 搜索區在右，左邊是同伴：不動
2. 搜索區在左，左邊是同伴：跨過同伴搜尋
3. 搜索區在右，右邊是同伴：跨過同伴搜尋
4. 搜索區在左，右邊是同伴：不動

簡單來說便是依據搜索區在哪裡判斷可不可以少找一個。
搜索區位置則是可以用長度判斷，如果是偶數那必定沒有孤單一個的，應該挺好理解。
程式碼如下


int singleNonDuplicate(int* nums, int numsSize){
    int start = 0;
    int end = numsSize-1;
    while(start < end){
        int cur=(start+end)/2;
        if (cur%2==0){
            if(nums[cur]==nums[cur-1]){
                end=cur-2;
            }
            else if(nums[cur]==nums[cur+1]){
                start=cur+2;
            }
            else break;
        }
        else{
            if(nums[cur]==nums[cur-1]){
                start=cur+1;
            }
            else if(nums[cur]==nums[cur+1]){
                end=cur-1;
            }
            else break;
        }
    }
    return nums[(start+end)/2];
}

## 優化
可以很明顯發現上面的判斷式很多，但實際上狀況不會那麼多，其實不用想的那麼複雜。
同樣可以用長度來判斷搜索區，假設搜索區是偶數長度，那最邊邊的格子必定和pivot相同，於是我們只需要比較一邊的鄰居就好，狀況分為以下幾種：
**1.** piovt在偶數格，代表左右分別有偶數個
**2.** piovt在奇數格，代表左右分別有奇數個
因為其他數字都是成對的，我們可以以pivot為中心把數列分成奇數列和偶數列的組合，只需要搜尋奇數數列即可。

int singleNonDuplicate(int* nums, int numsSize){
    int start = 0;
    int end = numsSize-1;
    while(start < end){
        int mid=(start+end)/2;
        if (mid%2==1){mid++;}
        if (nums[mid]==nums[mid-1]){
            end=mid-2;
        }
        else start=mid;
    }
    return nums[(start+end)/2];
}