Python O(log n) Binary search


  • 0
    D

    Approach #1 Binary search [Accepted]

    Intuition

    It is a search problem request O(log n) time and O(1) space

    Algorithm

    Binary search is suitable method for search problem and its
    time cost is O(log n)

    The basic idea is that the single element is not the same as the left one and
    the right one.

    First, if the length of array is 1, the only element is the answer we are looking
    for.If not, we do as follows.First We find the middle one of array,and assume if it
    is single element or not.If it is not the single element, there are four possibilities.

    Shown as follows:

    Divide parts is odd and right one is different:[1 1 2 2 3 3 5] The middle element
    is 2, it divides the array into two parts,[1 1 2] and [3 3 5](contain 3(odd) elements)
    right of middle element is 3 which is not equal to 2. The answer is in [3 3 5].

    Divide parts is odd and left one is different:[1 1 2 3 3 5 5],parts are [1 1 2] and
    [3 5 5],the answer is [1 1 2]

    Divide parts is even and right one is different:[1 2 2 3 3 5 5 6 6],parts are [1 2 2 3]
    and [5 5 6 6],answer is in [1 2 2 3] which contain the same number 3 as the middle one.In this
    situation we just need to put [1 2 2] into recursive function

    Divide parts is even and left one is different:[1 1 2 2 3 3 5 5 6],parts are [1 1 2 2]
    and [3 5 5 6],then we put [5 5 6] into recursive function

    Python

    class Solution(object):
        def singleNonDuplicate(self, nums):
            if(len(nums)==1):
                return nums[0]
            mid_place = len(nums)/2
            mid = nums[mid_place]
            if (mid!=nums[mid_place-1] and mid!=nums[mid_place+1]):
                return mid
            if(mid_place%2==0):
                if (mid!=nums[mid_place-1]):
                    return self.singleNonDuplicate(nums[mid_place+2:])
                return self.singleNonDuplicate(nums[:mid_place-1])
            if (mid!=nums[mid_place-1]):
                return self.singleNonDuplicate(nums[:mid_place])
            return self.singleNonDuplicate(nums[mid_place+1:])
    

    Complexity Analysis

    • Time complexity : O(n).
    • Space complexity : O(1).

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.