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
        

实现结果