河南快速网站备案,东莞公司注册服务平台,phpnow搭建本地网站,信誉好的合肥网站建设二分法
简介
和双指针一样#xff0c;二分法也是一种优化方法#xff0c;或者说二分法就是双指针的一类。不过#xff0c;二分法的思想比双指针诞生更早也更广泛#xff0c;在我们日常生活里也无时不刻在使用二分的思想。
比如我们想回顾某些影片#xff0c;但是只记得… 二分法
简介
和双指针一样二分法也是一种优化方法或者说二分法就是双指针的一类。不过二分法的思想比双指针诞生更早也更广泛在我们日常生活里也无时不刻在使用二分的思想。
比如我们想回顾某些影片但是只记得影片的大概日期我们往往会翻到最后一页根据最后一页的日期再来取中估算出想找的影片可能对应的页数通过不断重复来不断去定位影片的位置。 对于我们正常人来说这种索引是灵活的我们可以根据自己的需求来灵活调整二分的方法。比如最后一页是100我们在脑海里估算的时候如果影片比较早我们可能会定位到70页如果影片是最近才出的我们可能会定位到30页
但是对于计算机二分的算法是无法在程序进行的过程中调整的。也正因如此二分会带来很多细节上的问题——死循环越界等等这也是二分最令人头疼的地方。但是二分作为一个将时间复杂度O(n)降为O(log n)的方法在很多题中都作为了普遍的优化方法所以单单研究出二分不是为了解决某种具体的问题而是为将二分的思想运用到很多场景中。
朴素二分
朴素二分就是我们在初学很多语言第一次接触到的二分。
举一个很简单的例子704. 二分查找 - 力扣LeetCode 从一个有序数组中找到某个确定的值最简单暴力的方法就是直接遍历时间复杂度O(n)。但是从双指针的思想里我们很容易发现我们可以一边搜寻一边排除。
比如我们想找到5这个元素我们一开始便随便选一个元素下标假设我们选择了元素9的下标。 找到9以后将9和目标值比较显然9是比5要大的。但是数组又是升序我们就不需要考虑9以后的元素只用在9前面的元素中再去找5。这样做的好处是什么这样做显然将时间复杂度缩小了一半。 而我们不断重复这个过程时间复杂度不断缩减为一半最终时间复杂度就降为了O(log n)
同时用某种方法可以证明每次随便选择的数选择最中间的那个数期望效率是最高的具体证明方法就不解释了因为我也不会。 简单用代码实现一下
int l0;//左边界从0开始
int rnums.size()-1;//右边界从最后一个元素开始while(lr)//循环条件左边界在右边界左边
{int midl(r-l)/2;//二分取中if(nums[mid]target)//如果找到了返回该下标return mid;else if(nums[mid]target)//如果找到的数小于目标值意味着mid和mid左边的值都不满足条件lmid1;//从mid右边继续寻找else//如果找到的数大于目标值意味着mid和mid右边的值都不满足条件rmid-1;//从mid左边继续寻找
}
//如果循环结束了代表所有数都不满足条件那么退出循环返回-1return -1;
但是既然叫他朴素二分那自然意味着朴素二分只能解决一小部分问题。朴素二分太过老实了只要问题场景一换那么朴素二分就会出很多bug 把例子稍微换一下 边界二分
此时发现我们最朴素的二分已经不够用了。但是是不是二分就完全用不上了呢 在这里纠正一个很多人最常见的误区 二分不是只有数组顺序的时候才可以使用 而是只要数组能满足区间规律 就可以用二分来解决。 就比如在这里虽然朴素二分用不上了但是因为数组还是满足一个条件 所以还是可以根据二分的思想来找到每一个区间。
此时我们想找到等于二的左区间我们还是取二分中值的元素发现等于2 这也代表着我们找到了等于2的区间中的一个元素但是这却不一定是左边界因为这个2可能会有三种情况
为左边界为中间的某个元素为右边界
不过无论是哪一种情况都会对应一个结果mid右边一定不存在我们想找的左边界我们让rightmid再来进行一次寻找。
但是为什么right不能等于mid-1?因为mid可能就是左边界如果right等于mid-1那么就越过了左边界找不到结果。 所以我们可以轻易得到
再来看其他两种情况 如果mid对应的元素小于target那答案一定在mid的右边也就是 如果mid对应的元素大于target那答案一定在mid的左边也就是
不过这里还有一个坑点while循环的条件是什么 我们来看这个情况 所以结束条件只能是lr
用代码实现一下
int l0;
int rnums.size();while(lr)
{int midl(r-l)/2;if(nums[mid]target)lmid1;elsermid;//因为rmid-1和rmid效率几乎没有区别所以合并成同一种情况
}return l;//出循环的时候一定是lr所以返回哪一个都无所谓
右边界二分
再把问题变一下 此时上面的方法又行不通了不过思考的方式还是一样的。
我们找到一个二分中值mid可能有三种情况
nums[mid]target那右边界一定不在mid右边nums[mid]target那右边界一定在mid右边nums[mid]target那右边界一定在mid左边
总结下来还是那三种
if(nums[mid]target)rmid-1;//如果mid对应的值大于那么往左边找
elselmid;//和找左边界情况一样为了避免跳过答案所以一定不能为mid1
那是不是就这么简单解决了呢当然不是这又出现了一个新的坑点 怎么解决这个问题也很简单midleft(right-left1)/2就行了。
因为产生这个问题的根本原因就是当left和right相邻的时候mid应该是取left还是取right。我们直接从判断式来看 左边界是rmid但是为了避免死循环r一定要产生改变所以mid一定不能取r 右边界是lmid但是为了避免死循环l一定要产生改变所以mid一定不能取l 所以在这里我们的mid一定要取right对应的值而这个问题说人话就是向下取整和向上取整的问题。
用代码实现一下
int l0;
int rnums.size();while(lr)
{int midl(r-l1)/2;//向上取整if(nums[mid]target)rmid-1;elselmid;
}return l;//出循环的时候一定是lr所以返回哪一个都无所谓
边界总结和模板
说了这么多左边界和右边界其实有着很大的共性
循环条件一定是lr出循环的时候最终都会为lr无论返回哪一个都一样
但是我们怎么判断左边界和右边界的区别什么时候用什么代码
其实只需要考虑两个问题
1.是大于等于还是大于
我们来看一下右边界情况的语言描述 不在右边也就是代表着包含着当前的元素也就对应着lmid在右边和在左边也就是和代表着不包含当前的元素也就对应着lmid1和rmid-1 而说白了也就是个最简单的数学表达式描述问题我们只需要看着文字然后转换成数学式小学生都会。
2.向上还是向下取整来避免死循环
在右边界二分的时候就已经详细说明了我们取mid的不同其实就是为了避免进入死循环而解决方法就是通过判断是lmid还是rmid来分别向上取整和向下取整。 所以最终可以总结出求左右边界的模板
int l0;
int rnums.size();while(lr)
{1.判断mid是向上取整还是向下取整2.列出三种情况然后分别转化成两个数学判断表达式
}return l;
所有二分问题都可以通过这个模板来解决。
而看完了这些再去尝试这道题只有自己亲自动手理解和解出来才表示完全掌握了二分模板。
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCodehttps://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
