个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创二分查找算法(4) _搜索插入位置
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
温馨提示:
1. 题目链接:
2. 题目描述 :
3. 解法(二分查找) :
算法思路 :
代码展示 :
结果分析 :
4. 二分算法模板总结
温馨提示:
这道题是直接使用了二分模板,轻松拿捏了这道题,如果你还不知道的话,自行去下篇博客
---二分查找算法(2) _在排序数组中查找元素的第一个和最后一个_模板-CSDN博客
1. 题目链接:
OJ链接:搜索插入位置
2. 题目描述 :
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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 <= 104-104 <= nums[i] <= 104nums为 无重复元素 的 升序 排列数组-104 <= target <= 104
注意:请必须使用时间复杂度为
O(log n)的算法。
3. 解法(二分查找) :
算法思路 :
因为这道题对时间复杂度有要求,所以这里就不写暴力算法,直接使用二分查找
由于题目中的数组是有序数组,我们可以利用数组的二段性,将数组分成两部分:
1. 数组中的数 <= target
2. 数组中的数 > target
这样我们就可以使用二分算法进行查找,直接套用我们之前已经讲解过的二分算法
代码展示 :
class Solution {
public:int searchInsert(vector<int>& nums, int target) {//分成两部分 [..., target) [target, ...]int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(nums[mid] <= target) left = mid;else right = mid - 1;}if(nums[left] < target) return left + 1;else return left;}
};
结果分析 :
这里我们的算法时间复杂度为: log(N)满足题目要求.
4. 二分算法模板总结
这里再次强调一下我们的二分算法模板(真的很好用!!!)
while(left < right){int mid = left + (right - left) / 2;if(...) left = mid + 1;else right = mid;
}while(left < right){int mid = left + (right - left + 1) / 2;if(...) left = mid;else right = mid - 1;
}快速记忆:
分类讨论的代码,就题论题即可
下面出现-1,上面就+1,否侧不加
