合肥网站排名提升,网站开发 如何定位,百度地图wordpress,网站推广软文选天天软文总结#xff1a;二分查找的目标有两个#xff0c;一个是左区件的右边界#xff0c;一个是右区间的左边界
如何去理解二分的过程#xff1f;
如果要查找的是左区间的右边界#xff1a;
可以将[l, r]理解一个集合#xff0c;这个集合范围内的数都有可能是最后需要得到的…总结二分查找的目标有两个一个是左区件的右边界一个是右区间的左边界
如何去理解二分的过程
如果要查找的是左区间的右边界
可以将[l, r]理解一个集合这个集合范围内的数都有可能是最后需要得到的目标值–左区间的右边界这个点
每次要做的事情就是去缩小更新这个集合最终使得集合里只有一个元素那个元素就是目标值
每一次用mid去找集合的中点有一个大前提结合的结构[需要的值的集合|不需要的值的集合] 为了方便理解这个集合我们可以理解为假设你有一个飞镖也就是mid有一个靶子就是这个数组靶子有内环边界点所在的区间或者说集合和外环我们要找的集合的补集靶子有一个中心点内环的边界也就是需要找到左区间的右边界。 mid的位置有两种情况落在左区间里或者落在右区间里
如果落在了左区间相当与告诉你了一个信息从这个地方包括这个地方mid所在的索引往后[mid, r]可能会发现右边界。与之对应的信息是右边界绝对不在mid左边的集合内[l, mid-1]所以左边的集合([l, mid-1])就可以被删掉了要实现这个操作只需要让下一次判断的集合是[mid, r]就i可以了等价于lmid如果落在了右区间相当于告诉了你这个点往右包括这个点都不是我要的区间需要被删掉。那就直接令l mid-1删除集合中绝对不是答案的那一坨也就是右边那一坨这样不断的往复删除确定的无用集合最后就可以得到一个目标集合。
对于查找到是右区间的左边界也是一个原理。
mid的计算是左偏还是右偏怎么去判断
关于mid的计算方式midij 1还是(midij1) 1个人有一种比较好理解的方法
同样分两种情况
找左区间右边界找右区间左边界
左区间右边界
首先要明白产生边界问题的原因在哪里
奇数个集合的时候对于两者mid都是指向中间元素但是如果集合个数是偶数他们的中点是谁很显然两者都不是中点1 中点是我 2中的那是1和2中间的文字吧。
所以要么去文字左边的1为中点要么取文字右边的2为中点。这样一来这个中点其实就不是真正意义上的中点了。
首先说结论取右边界需要右偏我们来分析一下 对于集合很大的时候是没有问题的边界问题只会发生在集合很小的时候所以只有拿出一个很小的集合一个快被处理结束的集合才能够知道为啥左偏会进入死循环为啥不能用它这个问题。 所以直接去分析两个元素时有哪些情况(O表示的是左区间右边界所在的集合X表示待删除的集合)
[O, O][X, X][O, X][X, O]
其中[X, O]这种情况不可能存在因为左区间的相对顺序一定在左边
左边界l是指向第一个元素的右边界r是指向第二个元素的
mid如果找到目标元素并不会剔除并不会缩小范围所以这个时候想要缩小范围就需要mid起作用了
对于[O, O]二分查找如果左偏会去看第一个元素包含它这没什么问题只要我们的mid下一次去往右看就行了但是问题就在于下一次mid看左边还是看右边是和左偏绑定在一起的所以如果左偏下一次mid还会看左边如果右偏下一次mid还会看右边但是我们需要看右边啊所以只能够右偏了这样遇到这种情况mid也能继续向右看去。
同样的对于右区间左边界的判断也是如此
[O, O]
其实说白了就是两个元素时找右边界时遇到需要的元素l会直接落在mid上进行更新。
找左边界时, 遇到需要的元素r会直接落在mid上进行更新为了防止更新后继续重合。 找右边界mid下一次查找只能偏右更新避开l防止死掉 找左边界mid下一次查找就只能偏左更新避开r防止死掉
