35. 搜索插入位置

思路：看着有序数组和目标值 定位二分查找和顺序查找 时间复杂度O（logn）考虑都不用考虑直接二分查找
考虑目标值不在数组里的情况

实例三
一开始中间下标为1对应3小于目标值，left=0+1=1
新的中间下标为2对应5小于目标值 left=2+1=3
对应新的中间下标为3 小于目标值 left=3+1=4 > right=3 循环结束 输出的是4
实例五
中间下标为0 对应1 大于目标值
right=middle-1 = -1 < left=0 循环结束 输出的0
由此可见 输出的可能是left
实例四
right一直在减小 由一开始的3 到 0 再到-1＜left=0 循环结束
输出0
由此可见输出的为left的值（not found）

一开始我思考的更加全面一点 返回的是max(left,right),AC了之后复盘结果发现left就可以AC

class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
# 左闭右闭
left, right = 0, len(nums) - 1
while left <= right:
middle = (left + right) // 2
if nums[middle] == target:
return middle
elif nums[middle] > target:
right = middle - 1
else:
left = middle +1
else:
return max(left,right)