Problem statement

https://leetcode.com/problems/single-element-in-a-sorted-array/

Solution

Straightforward way is to just iterate over all elements in O(n). There is smarter binary search solution. For example we have aa bb cc dd ee ff gg h ii jj kk. Let us find middle element, but shift it by one if number of element in the left part is odd: we always consider even number of elements in the left part. Then if nums[mid] == nums[mid-1] it means, that in the left part all elements are paired and we need to look in the right part. In the opposite case it means, that we need to look into the left half.

Complexity

Time complexity is O(log n), space complexity is O(1).

Code

class Solution:
    def singleNonDuplicate(self, nums):
        beg, end = 0, len(nums) - 1

        while end > beg + 1:
            mid = (beg + end)//2
            if (mid - beg) % 2 == 0: mid += 1  
            if nums[mid] == nums[mid - 1]: 
                beg = mid + 1
            else:
                end = mid 

        return nums[beg]