二分法,三分法,尺取法
二分法
二分法的主要内容就是对一个单调的区间进行二分,可以在很低的时间内快速确定答案的位置。
首先确定一个左端点和右端点,即可以得到一个中点mid=(L+R)/2 ,二分之后需要对中间点进行judge,进行正义的审判,确定该点是否可行。然后根据judge的结果缩小区间。
每次二分即可以把区间缩小一半。
尺取法
尺取法是模拟的虫子的蠕动。可以降低不必要的计算量。
在某些题目中可以将复杂度为n^2降低到n
三分法
三分法不同与二分法在于三分法适用于有“山峰”的题目,即题目的解是先升高,然后到一个最高点,之后再降低。
题目的目的就是求那一个最大值。
这时候还是需要一个L端点和R端点,但是需要两个mid点,一个mid点是(L+R)/2
另外一个mid2点是(mid+R)/2 即是3/4点。
这样通过比较两个mid点的大小,即可推断出来山峰的位置,从而缩小区间。
经过多次逼近后,即可求得题解。