三分只支持严格凸函数。比如要在函数 dd 上三分，函数 dd 定义域上的相邻位置（比如 p - EPS 和 p + EPS 或 p 和 p + 1）的值不同。如果相邻位置值相同可以用复杂度不正确的三分（详见「整数三分-非严格凸函数」）

整数三分

严格凸函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline int calc(int p) { /* ... */ }
int TDic() {
    int l = 1, r = cntmap, dis, lmid, rmid;
    while (l < r) {
        dis = (r - l) / 3;
        lmid = l + dis;
        rmid = r - dis;
        if (calc(lmid) <= calc(rmid)) {
            l = lmid + 1;
        } else {
            r = rmid - 1;
        }
    }
    return l;
}

非严格凸函数

最坏复杂度为 O(n)O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
inline int calc(int p) { /* ... */ }
int TDic(int l, int r) {
    int dis, lmid, rmid, calclmid, calcrmid;
    while (l < r) {
        dis = (r - l) / 3;
        lmid = l + dis;
        rmid = r - dis;
        calclmid = calc(lmid);
        calcrmid = calc(rmid);
        if (calclmid < calcrmid) {
            l = lmid + 1;
        } else if (calclmid > calcrmid) {
            r = rmid - 1;
        } else {
            int p1 = TDic(l, lmid), p2 = TDic(lmid + 1, rmid - 1), p3 = TDic(rmid, r);
            int calcp1 = calc(p1), calcp2 = calc(p2), calcp3 = calc(p3);
            if (calcp1 > calcp2) {
                return p1;
            } else if (calcp3 >= calcp2) {
                return p3;
            } else {
                return p2;
            }
        }
    }
    return l;
}

实数三分

P3382 【模板】三分法

1
2
3
4
5
6
7
8
9
10
11
12
inline double calc(double p) {/* ... */}
void TDic(double l, double r) {
    double mid;
    while (r - l >= EPS) {
        mid = (l + r) / 2;
        if (calc(mid - EPS) > calc(mid + EPS)) {
            r = mid;
        } else {
            l = mid;
        }
    }
}