Binary Search without trick of +/- 0.5, Python


  • 0
    B
    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]
    
        left=0
        right=len(A)-1
    
        def findR(left,right):
            while True:
    
                if left>right:
                    return -1
                if left==right:
                    if A[left]==target:
                        return left
                    else:
                        return -1
                mid=(left+right)//2
    
                if A[mid]>target:
                    right=mid
    
                elif A[mid]<target:
                    left=mid+1
    
                else:
                    if mid+1<len(A) and A[mid+1]>target:
                        return mid
                    else:
                        left=mid+1
    
        def findL(left,right):
            while True:
    
                if left>right:
                    return -1
                if left==right:
                    if A[left]==target:
                        return left
                    else:
                        return -1
                mid=(left+right)//2
    
                if A[mid]>=target:
                    right=mid
    
                elif A[mid]<target:
                    left=mid+1
    
    
        while True:
            if left>right:
                return [-1,-1]
            if left==right:
                if A[left]==target:
                    return [left,right]
                else:
                    return [-1,-1]
    
            mid=(left+right)//2
    
            if A[mid]<target:
                left=mid+1
            elif A[mid]>target:
                right=mid
            else:
                if A[left]==target and A[right]==target:
                    return [left, right]
                elif A[left]==target:
                     right=findR(mid,right)
    
                elif A[right]==target:
                    left=findL(left,mid)
    
                else:
                    right=findR(mid,right)
                    left=findL(left,mid)
    
                return [left,right]
    

    It is kind of long.. But purely binary search


  • 1
    B

    Your code is too long, this is mine, short and clear

    class Solution():
    def searchRange(self, A, target):
        res = [-1, -1]
        l = 0
        r = len(A) - 1
        while l <= r:
            m = l + (r - l) / 2
            if A[m] == target:
                res[0] = m
                r = m - 1
            elif A[m] < target:
                l = m + 1
            else:
                r = m - 1
        l = 0
        r = len(A) - 1
        while l <= r:
            m = l + (r - l) / 2
            if A[m] == target:
                res[1] = m
                l = m + 1
            elif A[m] < target:
                l = m + 1
            else:
                r = m - 1
        return res

Log in to reply
 

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