二分查找算法错失最优解的原因及优化方案问询

需求说明 #

需在复杂函数上执行二分查找，找到整数n使得computed_goal与给定goal匹配，优先寻求理论层面的认知厘清，同时需要实践示例。

原算法问题 #

原C++算法示例如下：

l = 0, h = 4000; // 二分查找的上下边界
while (l < h)
{
    n = (l + h) / 2;

    x = vars / n; // vars代表更复杂的计算，x依赖于n
        
    computed_goal = ax^4 + bx^3 + cx^2 + dx + c; // computed_goal依赖于n
        
    if (computed_goal < goal)
        l = n + 1;
    else
        h = n - 1;

    if (abs(computed_goal - goal) / goal < 0.01) // 检查相对误差是否在1%以内
        return n; // 成功匹配目标值！
    else
        return 0; // 迭代未达到期望精度
}

实际场景中该算法会错失最优解：当goal=970时，n=3001是使|computed_goal - goal|最小的最优解，但因computed_goal略大于goal，算法将h设为n-1直接排除该解，最终错误收敛到n=2999。

认知误区 #

曾被告知二分查找应排除已检查的端点，但这会丢失最优解，需明确背后的理论依据。

修复尝试 #

将边界更新逻辑改为：

if (computed_goal < goal)
    l = n;
else
    h = n;

算法陷入l=3000、h=3001的无限循环；改为while(l + 1 < h)可打破循环，但不确定是否引入新错误。

附原PHP实现代码（输出2999，最优解应为3001）：

function matchGoal(int $goal = 970): int
{
    $l = 0;
    $h = 3900;

    while ($l < $h)
    {
        $n = intdiv($h + $l, 2);
        $x = 8321100 / $n;
        $factor = 5.113233695 * pow($n / 3000, 2);

        $computed_goal = (((-8.16965E-10 * $x + -3.15457E-06) * $x + 0.008437163) * $x + 207.9079475) * $factor - 0.076934117;

        if ($computed_goal < $goal)
            $l = $n + 1;
        else
            $h = $n - 1;
    }

    $relative_error = 100 * abs($computed_goal - $goal) / $goal;
    return ($relative_error < 1) ? $n : 0;
}

// 输出2999，但最优解为3001
print matchGoal() . PHP_EOL; 

理论解析 #

1. 二分查找的核心前提：单调性 #

二分查找仅适用于目标函数随搜索变量单调变化的场景。在你的问题中，computed_goal(n)需随n单调递增或递减——这是二分查找能正确缩小搜索区间的基础，若函数不单调，二分查找无法保证找到最优解。

2. 为何不能随意排除已检查的端点？ #

原算法中，当computed_goal >= goal时设置h = n-1，直接丢弃了n这个候选点。但n可能恰好是误差最小的点（如示例中的n=3001）。二分查找的区间必须始终包含所有可能的候选解，因此：

• 若computed_goal(n)随n单调递增：
  • 当computed_goal < goal：需要更大的n，左边界应设为n（或n+1，取决于循环条件）
  • 当computed_goal >= goal：当前n可能是最优解，右边界应设为n，而非n-1
• 若函数单调递减，逻辑反向即可。

3. 无限循环的原因与解决 #

当边界更新为l=n和h=n时，若l与h相差1（如3000和3001），整数除法会导致n始终等于较小的l，若此时computed_goal(l) < goal，l不会变化，循环永远无法结束。

改用while(l + 1 < h)作为循环条件，当区间缩小到两个相邻整数时退出循环，之后手动检查这两个候选点（甚至邻点），即可避免无限循环，同时覆盖所有可能的最优解。

修正后的PHP实现 #

function matchGoal(int $goal = 970): int
{
    $l = 0;
    $h = 3900;

    // 循环直到区间缩小为相邻两个数
    while ($l + 1 < $h)
    {
        $n = intdiv($h + $l, 2);
        $x = 8321100 / $n;
        $factor = 5.113233695 * pow($n / 3000, 2);
        $computed_goal = (((-8.16965E-10 * $x + -3.15457E-06) * $x + 0.008437163) * $x + 207.9079475) * $factor - 0.076934117;

        if ($computed_goal < $goal) {
            // 需要更大的n，保留当前n的右侧区间
            $l = $n;
        } else {
            // 当前n可能是候选，保留当前n的左侧区间
            $h = $n;
        }
    }

    // 检查所有候选点（l、h，可根据需求添加邻点）
    $candidates = [$l, $h];
    $best_n = 0;
    $min_error = PHP_FLOAT_MAX;

    foreach ($candidates as $n) {
        if ($n <= 0) continue; // 避免除以0错误
        $x = 8321100 / $n;
        $factor = 5.113233695 * pow($n / 3000, 2);
        $computed_goal = (((-8.16965E-10 * $x + -3.15457E-06) * $x + 0.008437163) * $x + 207.9079475) * $factor - 0.076934117;
        $error = abs($computed_goal - $goal) / $goal;
        
        if ($error < $min_error) {
            $min_error = $error;
            $best_n = $n;
        }
    }

    // 检查是否满足精度要求
    return $min_error < 0.01 ? $best_n : 0;
}

// 输出最优解3001
print matchGoal() . PHP_EOL; 

内容的提问来源于stack exchange，提问作者Dennis