Single Element in a Sorted Array

此题要求时间复杂度O(lgn)，想了半天只想出来一个分治的算法，但是空间还是无法O(1)

class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        start, end = 0, len(nums)
        return self.helper(nums, start, end)[1]

    def helper(self, nums, start, end):
        if start == end - 1:
            return (True, nums[start])
        if start == end - 2:
            return (False, -1)
        mid = start + (end - start) / 2
        if nums[mid] == nums[mid - 1]:
            left = self.helper(nums, start, mid + 1)
            right = self.helper(nums, mid + 1, end)
            if left[0] or right[0]:
                return (True, left[1]) if left[0] else (True, right[1])
            return (False, -1)
        elif nums[mid] == nums[mid + 1]:
            left = self.helper(nums, start, mid)
            right = self.helper(nums, mid, end)
            if left[0] or right[0]:
                return (True, left[1]) if left[0] else (True, right[1])
            return (False, -1)
        else:
            return (True, nums[mid])

此题的二分解法很有趣，三刷继续研究