淘客怎么建网站做推广,asp 网站支持多语言,网络优化是干什么的,wordpress rt视频教程前言 作者#xff1a;小蜗牛向前冲 专栏#xff1a;小蜗牛算法之路 专栏介绍#xff1a;蜗牛之道#xff0c;攀登大厂高峰#xff0c;让我们携手学习算法。在这个专栏中#xff0c;将涵盖动态规划、贪心算法、回溯等高阶技巧#xff0c;不定期为你奉上基础数据结构… 前言 作者小蜗牛向前冲 专栏小蜗牛算法之路 专栏介绍蜗牛之道攀登大厂高峰让我们携手学习算法。在这个专栏中将涵盖动态规划、贪心算法、回溯等高阶技巧不定期为你奉上基础数据结构的精彩算法之旅。一同努力追逐技术的星辰大海。 目录
一、二分查找
二、二分的朴素模板
1、例题1
2、朴素模板
三、二分的万能模版
1、例题2
2、查找区间左端点
3、查找区间右端点
4、万能模板
5、题目练习 一、二分查找
二分查找是一种在有序数组中查找目标值的算法。它通过反复将待查找区间分成两部分并检查中间元素来进行查找以缩小搜索范围直到找到目标值或确定目标值不存在为止。这种算法的时间复杂度为 O(log n)其中 n 是数组的元素个数。
对于二分查找我们简单的理解就是通过二段性不断的排除不属于目标值的的算法。
而为什么我们不三分四分呢 尽管三分、四分等算法在某些特定情况下可能会有所优势但由于二分查找已经被广泛证明为高效且简单的解决方案因此通常情况下选择二分更为合适。这里和数学期望有关就不和大家证明了 二分算法看起来非常简单但是他的细节是非常多而且查看能力非常强大。
比如当我们要查找2^3242亿多,如果我们要暴力查找就要查找42亿多次但是二次就只要查找32次。
为了解决二分细节太多问题(特别是在处理复杂问题对边界情况的处理
二、二分的朴素模板
1、例题1
这里我们直接用力扣上的一道题目来引出 给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4示例 2: 输入: nums [-1,0,3,5,9,12], target 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1提示 你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。 这里是非常经典的二分运用在一个有序的数组中有序就说明有二段性 让我们排查目标值target,暴力就不提了那二分是如何解题的。 这时候结果区域就只剩5、9、12,然后继续二分排除。
这里就不在细说直接看代码。
class Solution {
public:int search(vectorint nums, int target){int left 0;int right nums.size()-1;while(leftright){int mid (leftright)/2;if(nums[mid]target){left mid1;}else if(nums[mid]target){right mid-1;}else{return mid;}}return -1;}
};
通过这道题目我们来总结一下朴素模板。
2、朴素模板 这里简单说明一下xnums[mid],t为目标值。
这里为了保证leftright 当x t-----left mid1------[left,right]当x t-----right mid-1------[left,right]当x t-----返回结果 从上面我们可以归纳出二分的朴素模版 while (left right){int mid left (right-left)/2;//防止溢出if (....){left mid 1;}else if (.....){right mid - 1;}else{.....;}}
细节处理 1、循环结束的条件 leftright可不可以 这里是一定不可以的 这里会漏掉当left和right都指向同一个元素的情况大家注意在[left,right]区间的值都是没有被排查的所以条件一定是lefright。 2、在计算mid的时候有时候我们会看到二种写法 int mid left (right-left)/2; int mid left (right-left1)/2; 对于二者的区别其实对奇数个元素是没有区别的因为中间值一定是唯一的。
但是对于偶数个元素的中间值mid就有区别了
可以看到mid 是第一种求法的时候取到是方框中左边的值第二中求法求到是右边的值。
对于这中朴素模板来说是没有区别的但是对后面的万能模版来说却非常重要。
三、二分的万能模版
1、例题2 给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1 输入nums [5,7,7,8,8,10], target 8
输出[3,4] 示例 2 输入nums [5,7,7,8,8,10], target 6
输出[-1,-1] 示例 3 输入nums [], target 0
输出[-1,-1] 提示 0 nums.length 105-109 nums[i] 109nums 是一个非递减数组-109 target 109 对于这道例题如果我们继续用前面的朴素二分算法模本版就要处理许多边界问题那么我们应该如何求简化我们的思路。
2、查找区间左端点
为了解决上面朴素二分在求上面情况可能会出现退化为暴力的情况这里我们换一个思路利用二分求我们要求区间的左端点。 这里我们就分为了上面二种情况但是仅仅到这里我们就可以求编写代码了吗我觉的是远远不够因为对于二分来说最复制的是其中的边界问题没有处理好就会出现一系列的死循环问题。
细节处理 循环条件 leftright?leftright? 这里的循环条件是1还是2,这里我们先说结论一定不能取等号(所以选择情况1)。为什么 对于情况1
当我们要查看的是有结果的也就是说在[leftright]区间内存在我们要的结果(左区间端点)
对于left,一直是想要跳出1这个区域的但是对于right就会在2区域内活动当leftrightret,就是等于了结果也就没有必要在进入循环(如果进行就会死循环因为midright)。
对于情况2
在想xt,那么right就要一直向左移动最终就会和left相遇这里就只要判断当前值是否和t相等即可没有必要进入循环如果进入就会出现死循环
对于情况3
在想xt,那么left就要一直向右移动最终就会和right相遇这里就只要判断当前值是否和t相等即可没有必要进入循环如果进入就会出现死循环
综合上所述 leftright的时候就是最终结果没有必要进入循环判断如果判断就会死循环 2、求mid的操作 int mid left (right-left)/2; int mid left (right-left1)/2; 这里也是选择1 ,为什么 当最后只有二个值的时候如果我们选择2求mid可以想一下mid就会指选择区域右边(前面已经解释过了)当是如果是xt的情况时候这时候就会出现rightmid[left,right]区间没有动而出现死循环。
而现在1就不会出现这种情况
代码实现
class Solution {
public:vectorint searchRange(vectorint nums, int target){int left 0;int right nums.size()-1;vectorint result {-1, -1};if(nums.size()0) return result;//处理边界情况while(leftright){int mid left(right-left)/2;if(nums[mid]target){left mid1;}else{right mid;}}//得到左区间的的下标,这里出来一定是leftrightint begin-1,end-1;if(nums[left]target){begin left;int i 0;//从left位置开始找右区间for(i left;inums.size();i){if(nums[i]!target)break;}end i-1;result[0]begin;result[1]end;}return result;}
};
3、查找区间右端点
对于找区间右端点和找左端点的本质上是一样的只是变了一种形式下面我们快速了解一下 这里不同点就是区间划分不一样了因为是找右端点所以当xt时候left在移动的时候不能超过区间所以最多到leftmid这的区间是当xt的时候其实是和朴素二分哪里right的移动是一样的。
对于查找区间右端点我们仍要关注二个细节 循环结束条件是leftrigtmid的求法是:left(right-left1) 这里至于是为什么可以参考区间左端点细节的解释这里就不过多解释。
代码实现
class Solution {
public:vectorint searchRange(vectorint nums, int target) {vectorint result{-1,-1};int left0,right nums.size()-1;//处理特殊情况if(nums.size()0) return result;while(leftright){int mid left(right-left1)/2;if(nums[mid]target) leftmid;else right mid-1;}//到这里肯定是leftrightint begin -1,end-1,i0;if(nums[left]target){end left;//在去找左端点for(i left;i0;i--){if(nums[i]!target)break;}begin i1;}result[0]begin;result[1]end;return result;}
};
4、万能模板
根据对二分朴素模本进一步升级我们可以写出二分的万能模版 但是核心其实是前面的分析过程而这个模版只是一个思路大家借鉴就好还是要理解二分是在具有二段性的情况使用的。
5、题目练习 搜索插⼊位置easy x 的平⽅根easy⼭峰数组的峰顶easy0〜n-1 中缺失的数字easy寻找峰值medium搜索旋转排序数组中的最⼩值medium
