LeetCode 35. 搜索插入位置 | Python

文章目录

35. 搜索插入位置题目解题思路代码实现实现结果

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

实现结果

---

---

文章原创，如果觉得写得还可以，欢迎关注点赞。微信公众号《书所集录》同步更新，同样欢迎关注。