自助建站自己要做网站的来看下做彩票网站推广

自助建站自己要做网站的来看下,做彩票网站推广,站长工具视频,办网各位好久不见#xff0c;不知不觉2025都快要结束了#xff0c;是时候来再总结一次算法#xff08;入门#xff09;的经验了。 最近笔者看标准算法库时#xff0c;注意到C算法库中只有两种二分查找的方法#xff1a;lower_bound和upper_bound#xff0c;分别用来查找第一…各位好久不见不知不觉2025都快要结束了是时候来再总结一次算法入门的经验了。最近笔者看标准算法库时注意到C算法库中只有两种二分查找的方法lower_bound和upper_bound分别用来查找第一个大于等于某个值的元素和第一个大于某个值的元素。只有“第一个大于等于”和“第一个大于”够用吗笔者想起了之前关于二分查找题的总结似乎都是错题总结而且条理很不清晰根本没有道出二分查找使用的真相。既然标准库只提供了这俩说明对于程序员的日常开发来讲有这两个二分查找是完全够用的。那些之前的技巧和花招只能说是花拳绣腿可以说都是这两种二分查找的变体。1、查找第一个大于等于目标值的元素的位置为了更好的理解二分查找干了什么我想把这个过程描述为“Left指针要跳过哪些元素”这是我们写对二分查找的关键。从我为数不多的算法题经验来看写二分查找的人分为两派“Left结果派”和“Update结果派”Left派习惯在循环结束后让left直接就是所寻找的目标值位置而Update派习惯在二分过程中不断更新至正确答案。我是觉得Left派更好懂而且结构清晰有对称美。如下查找第一个大于等于目标值的元素。int left 0; int right size()-1; //left派在leftright时跳出循环 while(right left){ int mid (left right)/2; //什么时候移动lefttarget在mid的右边 if(target nums[mid]){ //跳过所有的小于目标值的元素那最终就是第一个大于等于目标值的元素 left mid1; //二分查找法的左指针必须要移动mid1 } else{ right mid; } } return left;二分查找必须将left移动为mid1。如果保持left仅代替mid不移动的话由于mid向左偏移的特性势必让算法出现死循环的情况left在right的前一位。而在(nums[mid]target)条件下移动至mid1位置代表“left要跳过所有小于目标值的元素”所以最终left只会落在第一个大于等于目标值的元素的位置。除非是人为将mid的特性改为向右偏移此时是right必须靠向left来杜绝死循环。while(right left){ int mid (left right)/21; //特性改为向右偏移 //什么时候移动lefttarget在mid的右边 if(target nums[mid]){ left mid; } else{ right mid-1; } } return left;那这个查找到的就是最后一个小于等于目标值的元素相当于是第一个大于等于目标值元素的左右对称算法。此时我在往期图文已有记载但我根本记不住这么麻烦但其实最后一个小于等于目标值的位置就是“第一个大于目标值的位置 - 1”。根本不用记那么多只用会写开头说的那两种就好这就是标准库的高明之处。2、查找第一个大于目标值的元素的位置刚刚说了二分查找的关键就是“Left指针要跳过哪些元素”那查找第一个大于目标值的元素的位置就是“让Left指针跳过所有小于等于目标值的元素”。如下查找第一个大于目标值的元素。int left 0; int right size()-1; //left派在leftright时跳出循环 while(right left){ int mid (left right)/2; //什么时候移动lefttarget在mid的右边 if(target nums[mid]){ //跳过所有小于等于目标值的元素那最终就是第一个大于目标值的元素 left mid1; } else{ right mid; } } return left;我们观察发现两种查找的区别只在于Left指针跳跃的条件。仍然是保证了永远是Left指针移动至mid1right指针移动至mid。他们之间的不同仅仅在于要跳过的元素特性不同。在(nums[mid]target)条件下移动至mid1位置就是代表“left要跳过所有小于等于目标值的元素”那就是第一个大于目标值的元素。同理当人为改变特性为向右偏移是查找最后一个小于目标值的元素。相当于是和第一个大于目标值元素的左右对称算法。while(right left){ int mid (left right)/21; //什么时候移动lefttarget在mid的右边 if(target nums[mid]){ left mid; } else{ right mid-1; } } return left;这很麻烦额外需要记住right往左边跳的情况还要在二分时加上1还要right跳到mid-1。所以我们可以直接是找到第一个大于等于目标值的元素位置后减去1得到最后一个小于目标值的元素。3、查找最后一个小于目标值的元素的位置没错就是第一个大于等于目标值的位置 - 1。int left 0; int right size()-1; //left派在leftright时跳出循环 while(right left){ int mid (left right)/2; //什么时候移动lefttarget在mid的右边 if(target nums[mid]){ //跳过所有的小于目标值的元素那最终就是第一个大于等于目标值的元素 left mid1; //二分查找法的左指针必须要移动mid1 } else{ right mid; } } return left-1;4、查找最后一个小于等于目标值的元素的位置没错就是第一个大于目标值的位置 - 1。int left 0; int right size()-1; //left派在leftright时跳出循环 while(right left){ int mid (left right)/2; //什么时候移动lefttarget在mid的右边 if(target nums[mid]){ //跳过所有小于等于目标值的元素那最终就是第一个大于目标值的元素 left mid1; } else{ right mid; } } return left-1;而上述的几种查找基本上可以覆盖所有常规的二分查找默认从小到大排序。但是需要注意的是上述情况均没有考虑目标值在数组范围外的情况。如果要考虑目标值在数组范围外的情况直接用lower_bound或者upper_bound最终left是数组的左边界或右边界。此时完全可以根据left的位置和left位置的值是否满足条件进行剪枝可尝试LeetCode.74。5、总结综上所述对于查找第一个大于等于目标值的元素和查找第一个大于目标值的元素只有一个要点——left每次必须跳到mid1。而其余的两种变体完全可以通过这两种查找减一获得。遇到更复杂的变体只需考虑——我的left要跳过哪些元素就都可以迎刃而解。至于两种标准库算法。1、lower_boundlower_bound(nums.begin(), nums.begin(), value)返回第一个大于等于value的元素的迭代器因为是跳过所有小于目标值的元素写nums[mid]target时leftmid1。2、upper_boundupper_bound(nums.begin(), nums.begin(), value)返回第一个大于value的元素的迭代器因为是跳过所有小于等于目标值的元素写nums[mid]target时leftmid1。为啥要叫这两个名字lower_bound是第一个大于等于比upper_bound的位置要lower一些所以叫lower你细品。最近事务繁重时常抽不出身。希望本文能给像我一样的小白一些帮助祝福各位在2025剩下的时间里事事顺遂。那么晚安喵~