菏泽网站网站建设,如何拉下对手网站,软件公众号开发,外贸网站建设需要注意事项Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏#xff1a; 算法Joureny 上篇我们讲解了关于二分的朴素模板和边界模板#xff0c;本篇博客我们试着运用这些模板。 #x1f3e0; 搜索插入位置
#x1f4cc; 题目… Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk
(๑•́ ₃ •̀๑) 文章专栏 算法Joureny 上篇我们讲解了关于二分的朴素模板和边界模板本篇博客我们试着运用这些模板。 搜索插入位置 题目内容 搜索插入位置 题目解析 数组为一个升序数组。 与经典的二分查找不同的是如果找不到目标值啧应该返回它应该在数组中被插入的位置。 算法原理 通过题意,我们发现我们要找的插入的位置能将整个数组划分为两段区间一段是小于target的另一段是大于等于target的具有二段性因此可以采用边界模板进行搜索。但是需要注意的是如果target存在的话我们直接返回对对应下标就行如果数组没有要找的target如果最后leftright时left所在的值小于target此时下一个位置就是给target的返回left1,否则返回left相当于原本位置给了target。 参考代码
class Solution {
public:int searchInsert(vectorint nums, int target){//int left 0;int right nums.size() -1;while(left right){int mid left (right - left) / 2;if(nums[mid] target)left mid 1;elseright mid; }if(nums[left] target){return left 1;}return right; }
}; x的平方根 题目内容 x的平方根 题目解析 对于平方根不是整数的相当于是向下取整 本题数据范围为 0 x 2^31 -1用int可能会溢出因为会有平方的操作。 算法原理
✏️ 思路一暴力解法 暴力解法思路很简单就是遍历数组依次平方与x进行比较当遇到第一个平方比x大的数停下此时它的前一个数就是所需结果。 ✏️ 思路二二分查找 由于是向下取整所以我们要找的点最终能把数组划分为两部分左边的值平方小于等于x右边的值平方大于x,具有二段性采用右边界模板。但需要注意的是本题x可以取0算是一种情况直接返回0即可同时由于int可能会溢出所以最好数据类型采用long long。 class Solution {
public:typedef long long ll;int mySqrt(int x) {ll target x;ll left 0;ll right x;//右端点while(left right){ll mid left (right - left 1) / 2;//cout mid endl;if(mid*mid target){right mid -1;}elseleft mid;}return left;}
}; 山脉数组的峰顶索引 题目内容 山脉数组的峰顶索引 题目解析
本题保证数组都是山脉数组也就是有一个山峰数组内值先增大后减小。 算法原理 ✏️ 思路一暴力解法 暴力解法思路很简单直接遍历数组找最大值之后再返回下标即可。 ✏️ 思路二二分查找 我们可以看到这个数组并不严格有序但是由于山峰也就是峰值能把数组左边划分为在递增的(arr[mid] arr[mid-1]),右边部分划分为递减的(arr[mid] arr[mid-1]).因此具有二段性可以使用左边界也可以使用右边界模板因为峰值可以是在左边递增出来的也可以是在右边递减得到右边部分。 参考代码
class Solution {
public:int peakIndexInMountainArray(vectorint arr) {int left 0;int right arr.size() - 1;while(left right){int mid left (right - left) / 2;if(mid 1 arr[mid] arr[mid1]){left mid 1;}else{right mid;}}return left;}
}; 总结本节我们发现即使数组不有序我们仍然可以使用二分查找。当发现题目要我们求的能体现二段性时我们就可以尝试使用二分查找。
