35. 搜索插入位置
题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/search-insert-position
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
解题思路
思路：二分查找
在这道题，题目中说明给定一个经过排序的数组，同时给定一个目标值。题目中的要求：
- 如果目标值在数组中，返回其索引
- 如果目标值不在数组中，返回其会被顺序插入的位置。
这里我们如果用暴力解的话，时间复杂度为 O(n)。但是要找有序数组中插入元素位置这种问题，我们可以考虑使用二分查找。
在这里，我们使用二分查找，遍历循环的过程中， 排除不符合条件的部分，最终剩下的就是答案。针对本题，可能出现的情况：
- 因为目标值不一定存在于数组中，而且有可能目标值会被顺序插入到末尾。这里可以直接单独进行判断，返回数组的长度（也就是数组最末尾元素的下一个位置，如示例 3)
- 通过观察示例，我们可以发现，当数组中的元素值严格小于目标值，那么它一定不是解。
二分查找使用相对简单，但是比较容易出错的地方在于边界的约束（需要注意）。
具体的代码实现如下（含注释）。
代码实现
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
length = len(nums)
# 这里不单独判断目标值可能会被插入末尾的情况，统一进行判断
# 设定边界
left = 0
# 因为目标值可能会被插入末尾，所以右边界设为 length
right = length
while left < right:
# 开始进行二分查找
# 这里是向下取整，mid 是包含在 [left, mid] 中的
mid = left + (right - left) // 2
# 严格小于 target 的元素，一定不是解
if nums[mid] < target:
left = mid + 1
elif nums[mid] == target:
# 当数组存在与目标值相同的元素时，返回其索引
return mid
else:
right = mid
return left