My accepted O(2 * log(n)) solution, use the


  • 1
    M

    Use the answer of the "searchInsert" problem.

    The searchInsert function return the insert position of the target.

    If target in array, the range's left index is target's insert position, and range's right index is (target + 1)'s insert position - 1.

    class Solution:
    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return a list of length 2, [index1, index2]
    def searchRange(self, A, target):
        if type(A) != list:
            raise TypeError
    
        if A == []:
            return [-1, -1]
            
        a = self.searchInsert(A, target)
        if A[a] == target:
            return [a, self.searchInsert(A, target + 1) - 1]
        else:
            return [-1, -1]
    
    # @param A, a list of integers
    # @param target, an integer to be inserted
    # @return integer(target's insert position)
    def searchInsert(self, A, target):
        if type(A) != list:
            raise TypeError
    
        if A == []:
            return 0
    
        a, b = 0, len(A) - 1
    
        while a < b:
            c = a + ((b - a) >> 1)
            if target <= A[c]:
                if c == 0 or target > A[c - 1]:
                    return c
                b = c
            else:
                if c == len(A) - 1 or target <= A[c + 1]:
                    return c + 1
                a = c + 1
    
        if target <= A[a]:
            return a
        else:
            return a + 1

  • 0
    Y

    The problem requires O(logn), is O(log(n^2)) also ok?


  • 0
    M

    I think it's ok. Anyway, 2 is just a constant value.


Log in to reply
 

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