Accepted python solution based on bisection search


  • 0
    L

    The code is based on the bisection search: if there exists element that equal to the target, return the index of that element. If not, return the index of the first element that is larger than the target. Boundary condition: what if the target is larger than all elements? Given that input, the result from the bisection search is the index of the last element, and the code will increase that index by one to get the right answer.

    class Solution:
        # @param A, a list of integers
        # @param target, an integer to be inserted
        # @return integer
        def searchInsert(self, A, target):
            back,front,mid=0,len(A)-1,int((len(A))/2)
            while back<front:
                if A[mid]<target:
                    back,front=mid,front
                elif A[mid]>target:
                    front=mid-1
                else:
                    return mid
                mid=int((front+back+1)/2)
            if A[mid]<target:  # check the boundary condition: what if the target is larger than all elements?
                return mid+1
            return mid

Log in to reply
 

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