class Solution(object):

def searchInsert(self, nums, target):

"""

:type nums: List[int]

:type target: int

:rtype: int

"""

low, high = 0, len(nums)-1

if target > nums[-1]:

return len(nums)

if target < nums[0]:

return 0

if len(nums) == 1:

return 0 if target<= nums[0] else 1

while low < high:

mid = (low + high)/2

if target == nums[mid]:

return mid

elif target > nums[mid]:

low = mid + 1

else:

high = mid

return low