Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. Assume no duplicates in the array.

searchinsertposition.py

class Solution:
    # @param A, a list of integers
    # @param target, an integer to be inserted
    # @return integer
    def searchInsert1(self, A, target):
        for i,val in enumerate(A):
            if target <= val:
                return i
        return len(A)

    def searchInsert2(self, A, target):
        imin, imax = 0, len(A)-1
        while imax >= imin:
            imid = (imax - imin) // 2 + imin
            if target == A[imid]:
                return imid
            elif target < A[imid]:
                imax = imid - 1
            elif target > A[imid]:
                imin = imid + 1
        return imin