二分法和三分法的用处和区别

“啊 _{，三分你比二分多一分}”

最近在做题的时候发现原来还有三分法这个东东，由于本人水平有限知道应该二分可以解决，但是由于最优解的函数并不单调我不知道怎么继续分了。看了题解才发现原来三分这么好用，看来不只是简单的“比二分多一分啊”

有一篇博文写的很好三分法与二分法的区别和三分法总结
先说说二分法：
二分法搜索法就是不断缩小解可能存在的范围，从而求得问题最优解的方法。
就是把[L,R]区间为两个区间，[L,mid]和（mid,R]。看中间值mid，是否为合法解，然后不断缩小区间直到满足范围。
用法：
1.从有序数组中查找某个值。
2.求最优值（前提是可以对目标函数进行试探，并且这个函数必须是单调的）

那么问题来了，并不是每次目标函数都是单调的，比如：（图有点丑 ）

我们要求的最优值在位置x，我们怎么进一步确定[L,R]区间呢？这里就要用到三分法了！

当我们求的目标函数不是单调函数（区间内递增/递减）就要使用三分法了，或者你重新构造一个单调函数使用二分也是可以的。

三分法：
1.将区间分为如下：

m1=L+(R-L)/3;
m2=R-(R-L)/3:

2.缩短区间

以求最大值为例，比较目标函数值f(m1)和f(m2)谁更靠近极值f(x)，如果f(m1)更靠近极值f(m1)>f(m2)，说明极值在[m1,r]之间，即左区间改为m1,否则右区间改为m2。