二分和三分

文章目录

二分原理代码： 三分原理代码

二分

二分，一个简单而神奇的算法，可以简化时间复杂度，但是用二分有一个条件，就是我们进行二分的序列必须有单调性。

原理

我们直接上一个栗子：从一个单调上升序列$a$中找一个数$x$（保证$x$一定存在）。

我们可以用朴素算法，直接从头到尾找一遍，时间复杂度$O(n)$。 如果当序列$a$的长度十分大时，这种方法就不好用了。

二分横空出世。 我们每次寻找左右边界的中间。 如果这个数大于$x$，右边界就等于中间。 否则，左边界就等于中间。 知道找到答案。

代码：

#include <bits/stdc++.h> using namespace std; int n,a[1005],x; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&x); int l=1,r=n; while(l<r) { int mid=(l+r)>>1; if(a[mid]>x) r=mid-1; else if(a[mid]==x) { printf("%d",mid); return 0; } else l=mid; } return 0; }

在二分过程中，每次都把查询的区间减半，因此对于一个长度为$n$的数组，至多会进行$O(logn)$次查找，从而起到简化时间的作用。

三分

三分可以在一个单峰函数中找出其凸点或凹点。

原理

我们就是把$[l,r]$区间分成三份，如果$f(midl)>f(midr)$,则$r=midr$；否则$l=midl$（这是求凸点）。 这看起来跟二分很想。 当$f(midl)>f(midr)$，仔细思考一下，当$f(midl)>f(midr)$时，$midr$一定在凸点右边，所以我们把$r=midr$。 否则，我们就把$l=midl$，这也十分好理解。

代码

第一种写法

double three_divide(double l,double r) { while(r-l>=eps) { double midl=(l+r)>>1,midr=(midl+r)>>1; if(f(midl)>f(midr)) r=midr; else l=midl; } return f(l); }

第二种写法

double three_divide(double l,double r) { while(r-l>=eps) { double midl=l+(r-l)/3,midr=r-(r-l)/3; if(f(midl)>f(midr)) r=midr; else l=midl; } return f(l); }

但其实没有啥区别。