八. Array 3 Search Insert Positio

Idea: use the Binary search

Calculating Time complexity:
assumption--> O(n) = logn ---- (1)
import (1) into T(n) = T(n/2) +b, then we get 'logn = log(n/2) + b
=> logn = logn - log2 +b
So, Assumption is valid.

class Solution:
    """
    @param A: an integer sorted array
    @param target: an integer to be inserted
    @return: An integer
    """
    def searchInsert(self, A, target):
        # write your code here
        self.index = 0
        def search_deep(A, target):
            # in case that A is []
            if not A:
                return self.index
            # if len of array is even, take the right side one as mid always
            mid = int((len(A) + 1)/2)
            # right might be enpty
            left = A[0:mid]
            right = A[mid:]
            # when there is no element with the same value as target's
            if not right and A[0] < target:
                return self.index +1
            # when element with the same value has been found 
            if not right:
                # only one element left
                return self.index
            else:
                if A[mid] == target:
                    # only three or two elements left
                    self.index +=mid
                    return self.index
        
            if target < A[mid]:
                return search_deep(left, target)
            else:
                self.index +=mid
                return search_deep(right, target)
                
        return search_deep(A, target)