(弱,算了,先放全部吧。。。)
先从枚举开始吧
大家最喜欢,也有些时候最讨厌,最烦人的算法
诶,比如说,有一列数,现在要找一个特定的,怎么办?
这个时候,大佬发话了:先排序。。(嘴被捂住)这个东西以后再说
我们可以一个一个的查过去
比如:1 3 2 5 4 9 7
找5
那么就是一个一个的找
1,不是;3,不是;2,不是。
好,5,是的
非常直接,非常有效,但是。。。时间的问题比较大(来一个1e7的,你就别提下一步了,这个东西都容易超时)
那么。。。怎么办呢?
评论区间
施工中🚧
好,大佬继续说:可以先排序,sort(),再用while。。。
其实吧。。。这样比较烦
通俗一点
就是:做两个界限
一个一开始很小,一个一开始很大
大佬:从此!我确定!这个要找的数,就在这个框里!
所以,我们需要缩小框,确定位置
怎么办呢?
既然一个区域很难办,那么我们就搞一个点,单点比较!
这个点,经过商议,两界限的中间那个点是最好的
大佬:插一句:用这个公式:lft+(rit-lft)/2,不容易爆int
直接说结果:如果这个点,比要找的数小,那么左边的界限就可以移动到中间的点
因为:中间的点都比目标小,左边界限在继承位置之后,也一定!比目标小
这个算法的核心!是排序了!不然也没办法通过一个点的比较推算出整一块区间
嗯嗯,就这么简单。。。吧?
其实难点还是挺多的,可以去洛谷上做几道板子
也可以用upper_bound和lower_bound
区别:前者是第一个出现的(小于等于)
后者是第一个大于的
但是,现在呢,这个东西。。。
也就是数组。。。多了一个东西。。。
难以处理啊
登录后才能进行此操作