# 【LeetCode】 540. 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. Find this single element that appears only once.

> Note: Your solution should run in O(log n) time and O(1) space.

> 給你一個整理過的陣列，其元素只包含出現兩次的整數和只有一個只出現一次的整數。找到那個單獨只出現一次的元素。

> 注意：
> 你的答案應該在O(log n)的時間複雜度和O(1)的空間複雜度之中。

## Example:

Example 1:

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


Example 2:

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

## Solution

* 可以先看看[這題](https://hackmd.io/@Zero871015/LeetCode-136)，比較一下兩題的差異：
* 本題有排序過
* 本題時間複雜度需求拉到O(log n)
* 而從排序過和O(log n)就應該很直覺地想到二分搜尋法。
---
* 我們可以將情況分為幾種情形：
1. 中間數剛好就是目標
2. 中間數不是目標
1. 中間數的左/右分別有奇數個數字
1. 中間數和前面的數字一樣
2. 中間數和後面的數字一樣
2. 中間數的左/右分別有偶數個數字
1. 中間數和前面的數字一樣
2. 中間數和後面的數字一樣
* 基本上從範例測資就可以想出並列出上面的這些情形，至於為什麼要考慮到奇數偶數呢？
* 那是為了確保新的範圍總個數為奇數，如果不是奇數就無法判斷誰是單獨的了。
* 接著就從範例中分析出新的範圍應該取哪裡(有些需要包含中間數，有些不用)，最後再加上`終止條件起始等於終點`即可。

### Code

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

###### tags: `LeetCode` `C++`