# 540. Single Element in a Sorted Array
###### tags: `Leetcode` `Medium` `Binary Search`
Link: https://leetcode.com/problems/single-element-in-a-sorted-array/
## 思路 $O(logN)$ $O(1)$
binary search
Suppose array is [1, 1, 2, 2, 3, 3, 4, 5, 5]
we can observe that for each pair,
first element takes even position and second element takes odd position
for example, 1 is appeared as a pair,
so it takes 0 and 1 positions. similarly for all the pairs also.

this pattern will be missed when single element is appeared in the array.

所以我们就是要找第一个miss掉这个pattern的数字就是答案

Q: 为什么end的起始值是nums.length-1，而不是nums.length呢？
A: 因为如果用nums.length的话，nums = [1]，就会出问题
Q: 但这样搜寻的范围变成了左闭右开区间0到nums.length-1，为什么还是能找到正确答案呢
A: 因为在其他情况下start的范围是0到nums.length，但这题start的范围只有0到nums.length-1，也就是说它一定能找得到答案，**只有一定能找得到答案的时候才可以把end从nums.length改成nums.length-1**
这里类似于[0162. Find Peak Element](https://hackmd.io/NoxhXDOETuOXKM72I9hFhw)
## Code

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        while(start<end){
            int mid = (end-start)/2+start;
            if((mid%2==0 && nums[mid]==nums[mid+1])||(mid%2==1 && nums[mid-1]==nums[mid])){
                start = mid+1;
            }
            else{
                end = mid;
            }
        }
        return nums[start];
    }
}