三分查找

求单峰区间的极值

整数三分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 求极大值 [l,r]
int find(int l, int r) {
int m1, m2, val = 0, ret;
while (r - l >= 3) {
m1 = l + (r - l) / 3;
m2 = r - (r - l) / 3;
if (work(m1) > work(m2))
r = m2;
else
l = m1;
}
for (int i = l; i <= r; i++) {
int res = work(i);
if (val < res) val = res, ret = i;
}
return ret;
}

浮点三分

1
2
3
4
5
6
7
8
9
10
11
12
13
// 求极小值
double find(double l, double r) {
double m1, m2;
while (r - l >= eps) {
m1 = l + (r - l) / 3;
m2 = r - (r - l) / 3;
if (work(m1) > work(m2))
l = m1;
else
r = m2;
}
return (m1 + m2) / 2;
}