Can solution be obtained in one pass


  • 0
    D

    I was able to solve the problem in 2 passes. One for lower bound the other for upper bound. Is the solution possible in one pass. Overall complexity remains same though.


  • 9
    U

    My Python code is one pass, isn't it?

    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 not A:
            return [-1, -1]
        return self.search(A, 0, len(A)-1, target)
    
    def search(self, A, start, end, target):
        if A[start]>target or A[end]<target:
            return [-1, -1]
        if A[start] == target and A[end] == target:
            return [start, end]
        m = start+(end-start)/2
        l = self.search(A, start, m, target)
        r = self.search(A, m+1, end, target)
        if l == [-1, -1] and r == [-1, -1]:
            return [-1, -1]
        if l == [-1, -1]:
            return r
        if r == [-1, -1]:
            return l
        return [l[0], r[1]]

  • 0
    S

    I don't think so. Because there is recursion in it.


  • 0

    I agree it's not one "pass", but "there is recursion" is insufficient reason. You could write ordinary binary search as recursion, and it would be one "pass". The full reason is that the two recursive calls can lead to two separate paths of length O(log n), which I consider two passes. Only two, though. This doesn't explode exponentially as one might think at first sight.

    This is a quite neat algorithm and I took the liberty to rewrite and explain it and its runtime here.


Log in to reply
 

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