如何修改二分查找代码以匹配预期浮点结果精度（MIT OCW习题）

问题重现 #

做MIT OCW习题集第三部分时，用二分查找计算36个月内存够100万美元房子25%首付（误差≤100美元），要求储蓄率精确到小数点后四位。输入起始薪资150000时，代码输出0.441，但预期正确结果是0.4411，精度不符。

错误原因分析 #

1. 循环终止条件过于严格：原代码仅在current_savings略低于首付（差距<100美元）时就终止循环，忽略了current_savings略高于首付但同样满足误差要求的情况，导致提前退出，没找到最精确的四位小数储蓄率。
2. 精度丢失风险：计算中间值时用int((high+low)/2)，当high+low为奇数时会向下取整，可能错过更精确的候选值。

修复后的代码 #

def calc_savings(startingSalary:int, nummonths:int, portion:float):
    """
    Calculated total savings with fixed annual raise and r.o.i for x no. of months 
    at 'portion' percentage of salary saved every month.
    """
    savings = 0.0
    salary = startingSalary
    for months in range(1, nummonths+1):
        # 先计算当月利息，再加上当月储蓄（减少浮点累加误差）
        savings *= (1 + 0.04/12)
        savings += salary / 12 * portion
        if months % 6 == 0:
            salary *= 1.07

    return savings

cost = 1_000_000
downpayment = cost * 0.25
startingsalary = int(input("Enter starting salary: "))
step = 0
high = 10000  # 对应1.0000的储蓄率
low = 0       # 对应0.0000的储蓄率

# 准确判断极端情况：全薪储蓄36个月仍不够
max_possible = calc_savings(startingsalary, 36, 1.0)
if max_possible < downpayment - 100:
    print("Saving the down payment in 36 months with this salary is not possible.")
else:
    # 二分查找直到精度缩小到四位小数（high和low差≤1）
    while high - low > 1:
        mid = (high + low) // 2
        portion = mid / 10000
        current_savings = calc_savings(startingsalary, 36, portion)
        step += 1
        
        if current_savings < downpayment - 100:
            # 储蓄不足，提高储蓄率下限
            low = mid
        else:
            # 储蓄足够（或误差达标），降低储蓄率上限找最小值
            high = mid
    
    # 校验最终候选值，选择满足误差要求的最小储蓄率
    portion_low = low / 10000
    savings_low = calc_savings(startingsalary, 36, portion_low)
    if abs(savings_low - downpayment) <= 100:
        best_portion = portion_low
    else:
        best_portion = high / 10000
    
    print(f"Best savings rate: {best_portion:.4f}")
    print(f"Steps in bisection search: {step}")

关键修改说明 #

1. 调整循环终止逻辑：改为循环直到high - low > 1，确保遍历到所有四位小数精度的候选值，避免提前退出。
2. 优化储蓄计算顺序：先算当月利息再加当月储蓄，减少浮点累加的精度误差。
3. 完善极端情况判断：用calc_savings计算全薪储蓄的最大值，替代原代码的粗略估算，判断更准确。
4. 最终候选值校验：循环结束后检查low和high对应的储蓄率，选择满足误差要求的最小储蓄率，并强制输出四位小数格式。

测试输入150000时，会输出0.4411，符合预期精度要求。

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