搜索插入位置
- 题目
- 题目描述
- 示例 1:
- 示例 2:
- 示例 3:
- 提示:
- 题目链接
- 题解
- 解题思路
- python实现
- 提交结果
题目
题目描述
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为 无重复元素 的 升序 排列数组
-10^4 <= target <= 10^4
题目链接
搜索插入位置
题解
解题思路
这个问题可以通过二分查找算法来解决。二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且同样从中间元素开始比较。如果在某一步骤数组为空，则目标值不存在于数组中。这个搜索算法的时间复杂度为 O(log n)。
对于这个问题，如果目标值不存在于数组中，我们返回它应当被插入的位置。幸运的是，即使目标值不在数组中，二分查找的逻辑仍然可以帮助我们找到正确的插入位置。
下面是具体的步骤：
- 初始化两个指针
left和right分别指向数组的起始和结束位置。 - 进入循环，条件是
left <= right。 - 在每次迭代中计算中间点
mid。 - 如果
nums[mid]等于目标值target，则找到了目标值的位置，直接返回mid。 - 如果
target小于nums[mid]，则目标值应该位于左半部分，更新right = mid - 1。 - 如果
target大于nums[mid]，则目标值应该位于右半部分，更新left = mid + 1。 - 当循环结束时（即
left > right），此时left指针指向的就是目标值应该插入的位置，因为所有小于target的值都在left的左边，所有大于target的值都在left的右边。
python实现
下面是 Python 实现代码：
def searchInsert(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1else:right = mid - 1# At this point, `left` is the correct insertion indexreturn left
这段代码实现了二分查找，并且当找不到目标值时返回了正确的插入位置。时间复杂度为 O(log n)，空间复杂度为 O(1)。
提交结果
