'''
题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
例子

searchInsert([1,3,5,6], 5) -> 2
searchInsert([1,3,5,6], 2) -> 1
searchInsert([1,3,5,6], 7) -> 4
searchInsert([1,3,5,6], 0) -> 0
假设

输入的参数均不为空
tips

二分查找
代码
'''
···
def searchInsert(nums,target):
left, right = 0, len(nums)-1
# 先判断是否是边界外，节省时间
if target < nums[0]:
return 0
if target > nums[-1]:
return len(nums)
# 二分查找
while left <= right:
mid = (left + right)//2
if nums[mid] == target:
return mid
elif target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
print('left , right :',left, right)
return left
# pass

print(searchInsert([1,3,5,6], 5)) #-> 2

print(searchInsert([1,3,5,10], 2) )#-> 1
print(searchInsert([1,3,5,10], 4) )#-> 2
print(searchInsert([1,3,5,10], 7) )#-> 3

print(searchInsert([1,3,5,6], 7)) #-> 4

print(searchInsert([1,3,5,6], 0)) #-> 0

···