算法基础算法

三分查找

字数统计: 2.5k字   |   阅读时长: 11分
, , , ,

摘要: 三分的应用场景与代码模板，解决题目 1515、1095、852

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 二分 中，我们总结了二分的常见类型，其中主要是区间二分以及值域二分。之后进一步学习了 实数区间二分 和 实数值域二分。

本文我们学习一下三分查找。首先看一下实数三分算法，解决单峰函数求极值点的场景，并给出代码模板。然后以力扣 852 为例看一下整数三分算法，当然这道题也可以用二分来做。最后用三分算法解决两个力扣题目，1095 和 1515。

$0 实数三分查找

场景：单峰函数求极值点

分析: 三分查找

在定义域 [L, R] 上考虑凸函数，用三分查找的方式可以逐步将不可能包含最小值点的范围排除。算法如下：

  • 取 L < m1 < m2 < R，记 y1 = f(m1), y2 = f(m2)
    • y1 < y2: 最小值点一定不在 [L, m1]
    • y1 > y2: 最小值点一定不在 [m2, R]

代码模板：一元单峰函数求极小值点

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
const double EPS = 1e-10;

struct Function
{
    ...
    double operator()(double x) const
    {
        ...
    }
};

double ternary_search(Function& f, double L, double R)
{
    double l = L, r = R;
    while(l + EPS < r)
    {
        double m1 = l + (r - l) / 2.0;
        double m2 = m1 + (r - m1) / 2.0;
        if(f(m1) < f(m2))
            r = m2;
        else
            l = m1;
    }
    return l;
    // return f(l);
}

$1 整数三分查找

场景：单峰山脉数组查找最大值

符合下列属性的数组 arr 称为 山脉数组 ：

  • arr.length >= 3
  • 存在 i（0 < i < arr.length - 1）使得：
    • arr[0] < arr[1] < … arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > … > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。

提示：

1
2
3
3 <= arr.length <= 1e4
0 <= arr[i] <= 1e6
题目数据保证 arr 是一个山脉数组

示例 1：
输入：arr = [0,1,0]
输出：1

示例 2：
输入：arr = [0,2,1,0]
输出：1

示例 3：
输入：arr = [0,10,5,2]
输出：1

示例 4：
输入：arr = [3,4,5,1]
输出：2

示例 5：
输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2

算法1：整数三分

将实数单峰函数求极值点的三分查找套过来是可以的，代码如下：

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int n = A.size();
        int l = 1, r = n - 2;
        while(l < r)
        {
            int m1 = l + (r - l) / 2;
            int m2 = (m1 + 1) + (r - (m1 + 1)) / 2;
            if(A[m1] > A[m2])
                r = m2 - 1;
            else if(A[m1] < A[m2])
                l = m1 + 1;
            else
            {
                l = m1 + 1;
                r = m2 - 1;
            }
        }
        return l;
    }
};

算法2：整数二分

对于离散下标的数组来说，找山脉的峰值点可以用二分做。

找到二分点 mid = (left + right) / 2 之后考察 A[mid] 和 A[mid + 1] 的关系

对比 A[mid] 与 A[mid + 1] 在实数场景下无法实现，因此只能用三分，整数情况下可以直接对比，则可以直接二分。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        int n = A.size();
        int left = 0, right = n - 1;
        while(left + 1 < right)
        {
            int mid = left + (right - left) / 2;
            if(A[mid - 1] < A[mid] && A[mid] > A[mid + 1])
                return mid;
            if(A[mid - 1] > A[mid])
                right = mid;
            else
                left = mid;
        }
        return -1;
    }
};

$2 题目

1095. 山脉数组中查找目标值

（这是一个 交互式问题 ）

给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。

如果不存在这样的下标 index，就请返回 -1。

何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：

首先，A.length >= 3

其次，在 0 < i < A.length - 1 条件下，存在 i 使得：

  • A[0] < A[1] < … A[i-1] < A[i]
  • A[i] > A[i+1] > … > A[A.length - 1]

你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：

  • MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始）
  • MountainArray.length() - 会返回该数组的长度

注意：

对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。

为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：https://leetcode-cn.com/playground/RKhe3ave，请注意这 不是一个正确答案。

提示：

1
2
3
3 <= mountain_arr.length() <= 10000
0 <= target <= 1e9
0 <= mountain_arr.get(index) <= 1e9

提示：

1
2
3
3 <= mountain_arr.length() <= 10000
0 <= target <= 1e9
0 <= mountain_arr.get(index) <= 1e9

示例 1：
输入：array = [1,2,3,4,5,3,1], target = 3
输出：2
解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。

示例 2：
输入：array = [0,1,2,4,2,1], target = 3
输出：-1
解释：3 在数组中没有出现，返回 -1。

算法：整数三分

  • 先用整数三分（整数二分也可以）求出山脉的峰值
  • 峰值左侧单调增，二分找目标值
  • 峰值右侧单调减，二分找目标值

代码 (C++)

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int n = mountainArr.length();
        // 三分查找，得最大值点
        int l = 1, r = n - 2;
        while(l < r)
        {
            int m1 = l + (r - l) / 2;
            int m2 = (m1 + 1) + (r - (m1 + 1)) / 2;
            int a_m1 = mountainArr.get(m1);
            int a_m2 = mountainArr.get(m2);
            if(a_m1 > a_m2)
                r = m2 - 1;
            else if(a_m1 < a_m2)
                l = m1 + 1;
            else
            {
                l = m1 + 1;
                r = m2 - 1;
            }
        }
        int max_idx = l;
        if(mountainArr.get(max_idx) == target)
            return max_idx;
        int left = _bisearch(0, max_idx - 1, true, mountainArr, target);
        if(left != -1)
            return left;
        int right = _bisearch(max_idx + 1, n - 1, false, mountainArr, target);
        if(right != -1)
            return right;
        return -1;
    }

private:
    int _bisearch(int l, int r, bool up, MountainArray &mountainArr, const int target)
    {
        while(l <= r)
        {
            int m = (l + r) / 2;
            int mx = mountainArr.get(m);
            if(mx == target)
                return m;
            else if(mx < target)
            {
                if(up)
                    l = m + 1;
                else
                    r = m - 1;
            }
            else
            {
                if(up)
                    r = m - 1;
                else
                    l = m + 1;
            }
        }
        return -1;
    }
};

1515. 服务中心的最佳位置

一家快递公司希望在新城市建立新的服务中心。公司统计了该城市所有客户在二维地图上的坐标，并希望能够以此为依据为新的服务中心选址：使服务中心 到所有客户的欧几里得距离的总和最小 。

给你一个数组 positions ，其中 positions[i] = [xi, yi] 表示第 i 个客户在二维地图上的位置，返回到所有客户的 欧几里得距离的最小总和 。

换句话说，请你为服务中心选址，该位置的坐标 [xcentre, ycentre] 需要使下面的公式取到最小值：

与真实值误差在 1e-5 之内的答案将被视作正确答案。

示例 1：
输入：positions = [[0,1],[1,0],[1,2],[2,1]]
输出：4.00000
解释：如图所示，你可以选 [xcentre, ycentre] = [1, 1] 作为新中心的位置，这样一来到每个客户的距离就都是 1，所有距离之和为 4 ，这也是可以找到的最小值。

示例 2：
输入：positions = [[1,1],[3,3]]
输出：2.82843
解释：欧几里得距离可能的最小总和为 sqrt(2) + sqrt(2) = 2.82843

提示：

1
2
3
1 <= positions.length <= 50
positions[i].length == 2
0 <= xi, yi <= 100

算法：实数三分

要求 $f(x, y)$ 的局部最小值，可以用寻找下降方向的梯度下降或者爬山法。

也三分查找，逐步缩小范围，直到找到最小值点。

给定的函数是二元的，外层的三分确定 x 的范围，分别固定 x 为 xm1, xm2 后，内层的三分进行最小值查找，将所得的最小值进行比较，进而排除对外层三分的某个范围 [xL, xm1], [xm2, xR]。

代码 C++ (模板: 二元单峰函数、三分套三分)

其中 Vector2 是二维向量的代码模板，参考文章：向量的实现。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
struct Function
{
    // 二元函数
    vector<Vector2> points;
    Function(vector<vector<int>>& p)
    {
        int n = p.size();
        points = vector<Vector2>(n);
        for(int i = 0; i < n; ++i)
        {
            points[i].y = p[i][1];
            points[i].x = p[i][0];
        }
    }
    double operator()(double x, double y) const
    {
        double ans = 0;
        Vector2 p0(x, y);
        for(const Vector2 &p: points)
            ans += (p0 - p).norm();
        return ans;
    }
};

struct PartialFunction
{
    Function f; // 二元函数
    double x;
    PartialFunction(Function& f, double x):f(f),x(x){}
    double operator()(double y) const
    {
        return f(x, y);
    }
};

double ternary_search(PartialFunction& f, double L, double R)
{
    double l = L, r = R;
    while(l + EPS < r)
    {
        double m1 = l + (r - l) / 2.0;
        double m2 = m1 + (r - m1) / 2.0;
        if(f(m1) < f(m2))
            r = m2;
        else
            l = m1;
    }
    return l;
}

double ternary_search(Function& f, double Lx, double Rx, double Ly, double Ry)
{
    double lx = Lx, rx = Rx, ly = Ly, ry = Ry;
    double y_max = 0.0;
    while(lx + EPS < rx)
    {
        double xm1 = lx + (rx - lx) / 2.0;
        PartialFunction f1(f, xm1);
        double ym1_max = ternary_search(f1, ly, ry);
        double xm2 = xm1 + (rx - xm1) / 2.0;
        PartialFunction f2(f, xm2);
        double ym2_max = ternary_search(f2, ly, ry);
        if(f(xm1, ym1_max) < f(xm2, ym2_max))
        {
            y_max = ym1_max;
            rx = xm2;
        }
        else
        {
            y_max = ym2_max;
            lx = xm1;
        }
    }
    return f(lx, y_max);
}

class Solution {
public:
    double getMinDistSum(vector<vector<int>>& positions) {
        Function f(positions);
        int Lx = positions[0][0], Rx = positions[0][0];
        int Ly = positions[0][1], Ry = positions[0][1];
        for(vector<int>& p: positions)
        {
            Lx = min(Lx, p[0]);
            Rx = max(Rx, p[0]);
            Ly = min(Ly, p[1]);
            Ry = max(Ry, p[1]);
        }
        if(Lx == Rx && Ly == Ry)
            return 0.0;
        if(Lx == Rx)
        {
            PartialFunction pf(f, Lx);
            return ternary_search(pf, Ly, Ry);
        }
        return ternary_search(f, Lx, Rx, Ly, Ry);
    }
};
Share