三分答案

问题描述

三分答案是一种用于查找单峰/单谷函数极值的搜索算法。通过将区间分成三份，比较两个三分点的函数值来确定极值的位置。

整数三分

算法思想

确定答案的取值范围[left, right)
取两个三分点 mid1 和 mid2
比较两点函数值确定搜索方向
每次排除三分之一的区间

代码实现

c++
java
python

class Solution {
public:
    int getValue(vector<int>& nums, int x) {
        // 计算在位置x处的函数值
        int value = 0;
        for (int i = 0; i < nums.size(); i++) {
            value += abs(nums[i] - x);
        }
        return value;
    }
    
    int findMin(vector<int>& nums) {
        int left = *min_element(nums.begin(), nums.end());
        int right = *max_element(nums.begin(), nums.end()) + 1;
        
        while (right - left >= 3) {
            int len = right - left;
            int mid1 = left + len / 3;
            int mid2 = right - len / 3;
            
            if (getValue(nums, mid1) < getValue(nums, mid2)) {
                right = mid2;
            } else {
                left = mid1;
            }
        }
        
        // 暴力查找最后几个点
        int minValue = INT_MAX, ans = left;
        for (int i = left; i < right; i++) {
            int value = getValue(nums, i);
            if (value < minValue) {
                minValue = value;
                ans = i;
            }
        }
        return ans;
    }
};

class Solution {
    private int getValue(int[] nums, int x) {
        // 计算在位置x处的函数值
        int value = 0;
        for (int num : nums) {
            value += Math.abs(num - x);
        }
        return value;
    }
    
    public int findMin(int[] nums) {
        int left = Arrays.stream(nums).min().getAsInt();
        int right = Arrays.stream(nums).max().getAsInt() + 1;
        
        while (right - left >= 3) {
            int len = right - left;
            int mid1 = left + len / 3;
            int mid2 = right - len / 3;
            
            if (getValue(nums, mid1) < getValue(nums, mid2)) {
                right = mid2;
            } else {
                left = mid1;
            }
        }
        
        // 暴力查找最后几个点
        int minValue = Integer.MAX_VALUE, ans = left;
        for (int i = left; i < right; i++) {
            int value = getValue(nums, i);
            if (value < minValue) {
                minValue = value;
                ans = i;
            }
        }
        return ans;
    }
}

class Solution:
    def getValue(self, nums: List[int], x: int) -> int:
        # 计算在位置x处的函数值
        return sum(abs(num - x) for num in nums)
    
    def findMin(self, nums: List[int]) -> int:
        left = min(nums)
        right = max(nums) + 1
        
        while right - left >= 3:
            length = right - left
            mid1 = left + length // 3
            mid2 = right - length // 3
            
            if self.getValue(nums, mid1) < self.getValue(nums, mid2):
                right = mid2
            else:
                left = mid1
        
        # 暴力查找最后几个点
        min_value = float('inf')
        ans = left
        for i in range(left, right):
            value = self.getValue(nums, i)
            if value < min_value:
                min_value = value
                ans = i
        return ans

实数三分

算法思想

确定答案的取值范围[left, right)
设定枚举次数（通常100次足够）
取两个三分点比较函数值
每次排除三分之一的区间

代码实现

class Solution {
public:
    double getValue(vector<double>& points, double x) {
        // 计算在位置x处的函数值
        double maxDist = 0;
        for (double point : points) {
            maxDist = max(maxDist, abs(point - x));
        }
        return maxDist;
    }
    
    double findMin(vector<double>& points) {
        double left = *min_element(points.begin(), points.end());
        double right = *max_element(points.begin(), points.end());
        
        // 三分100次，相对误差约为(2/3)^100
        for (int i = 0; i < 100; i++) {
            double len = right - left;
            double mid1 = left + len / 3;
            double mid2 = right - len / 3;
            
            if (getValue(points, mid1) < getValue(points, mid2)) {
                right = mid2;
            } else {
                left = mid1;
            }
        }
        
        return left;
    }
};

时间复杂度分析

算法时间复杂度空间复杂度

整数三分	$\mathcal{O}(\log n \cdot C)$	$\mathcal{O}(1)$
实数三分	$\mathcal{O}(T \cdot C)$	$\mathcal{O}(1)$

其中 $C$ 是计算函数值的时间复杂度， $T$ 是三分次数（通常取100）。

应用场景

单峰函数极值
单谷函数极值
凸/凹函数最值
距离最值问题
最优分割点查找

注意事项

函数的单调性判断
三分点的选择
精度要求的控制
整数与实数的区分
边界情况的处理

常见变形

查找最大值

cpp
java
python

int findMax(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    
    while (right - left >= 3) {
        int len = right - left;
        int mid1 = left + len / 3;
        int mid2 = right - len / 3;
        
        if (nums[mid1] > nums[mid2]) {
            right = mid2;
        } else {
            left = mid1;
        }
    }
    
    int maxVal = nums[left];
    for (int i = left + 1; i <= right; i++) {
        maxVal = max(maxVal, nums[i]);
    }
    return maxVal;
}

class Solution {
    public int findMax(int[] nums) {
        int left = 0, right = nums.length - 1;
        
        while (right - left >= 3) {
            int len = right - left;
            int mid1 = left + len / 3;
            int mid2 = right - len / 3;
            
            if (nums[mid1] > nums[mid2]) {
                right = mid2;
            } else {
                left = mid1;
            }
        }
        
        int maxVal = nums[left];
        for (int i = left + 1; i <= right; i++) {
            maxVal = Math.max(maxVal, nums[i]);
        }
        return maxVal;
    }
}

class Solution:
    def findMax(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while right - left >= 3:
            length = right - left
            mid1 = left + length // 3
            mid2 = right - length // 3
            
            if nums[mid1] > nums[mid2]:
                right = mid2
            else:
                left = mid1
        
        return max(nums[i] for i in range(left, right + 1))

查找最小值

cpp
java
python

int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    
    while (right - left >= 3) {
        int len = right - left;
        int mid1 = left + len / 3;
        int mid2 = right - len / 3;
        
        if (nums[mid1] < nums[mid2]) {
            right = mid2;
        } else {
            left = mid1;
        }
    }
    
    int minVal = nums[left];
    for (int i = left + 1; i <= right; i++) {
        minVal = min(minVal, nums[i]);
    }
    return minVal;
}

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        
        while (right - left >= 3) {
            int len = right - left;
            int mid1 = left + len / 3;
            int mid2 = right - len / 3;
            
            if (nums[mid1] < nums[mid2]) {
                right = mid2;
            } else {
                left = mid1;
            }
        }
        
        int minVal = nums[left];
        for (int i = left + 1; i <= right; i++) {
            minVal = Math.min(minVal, nums[i]);
        }
        return minVal;
    }
}

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while right - left >= 3:
            length = right - left
            mid1 = left + length // 3
            mid2 = right - length // 3
            
            if nums[mid1] < nums[mid2]:
                right = mid2
            else:
                left = mid1
        
        return min(nums[i] for i in range(left, right + 1))