This is just a binary search, except when you cannot find the target, you should compare target with the numbers in the narrow-down range and decide which position should be inserted.

```
class Solution(object):
def searchInsert(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
L = len(nums)
begin = 0
end = L - 1
mid = (begin + end)/2
b, e, m = nums[begin], nums[end], nums[mid]
if m == target:
return mid
while 1:
if end - begin <= 1:
if nums[begin] == target:
return begin
elif nums[end] == target:
return end
# If not found, we should compare this target with elements in nums[begin:end + 1]. Note that here end - begin <= 1, so brute force search will be fine
if nums[begin] > target:
return begin
elif nums[end] < target:
return end + 1
else:
return begin + 1
if m < target:
begin = mid + 1
end = end
elif m > target:
begin = begin
end = mid - 1
else:
return mid
mid = (begin + end)/2
m = nums[mid]
```