为何二分查找实现方式不同会导致两种解法运行时差异巨大？

你的代码迟迟没有输出，核心是三个关键逻辑错误，和二分查找的边界定义关系不大，而是变量重置、储蓄率计算时机、终止条件缺失的问题：

1. 储蓄值未重置，导致计算完全错误 #

每次二分查找迭代时，你没有把savings清零。第一次循环计算的储蓄会被带到下一次迭代，导致后续所有的储蓄计算都是基于之前的累计值，完全偏离当前测试的储蓄率对应的真实结果，永远达不到终止条件。

2. 储蓄率在每月循环内重复计算 #

内层的36个月循环里，你每个月都调用bisection(low, high)重新计算储蓄率，这意味着每个月的储蓄率都在变化，根本不是在测试固定的储蓄率下36个月能攒多少钱。正确的逻辑应该是：先确定当前二分的储蓄率，再用这个固定值计算36个月的储蓄。

3. 缺失「无法达成目标」的判断 #

如果用户输入的工资太低，3年哪怕攒100%工资都不够首付，你的代码会进入无限循环，没有任何提示。

修正后的代码 #

def bisection(i: int, j: int):
    high = j
    low = i
    return (high + low) / 2

semiannualraise = .07
rmonthly = 0.04 / 12
cost = 1_000_000
downpayment = cost * 0.25
epsilon = 100
startingsalary = float(input("Enter Salary: "))

# 先判断是否有可能达成目标：攒100%工资3年够不够
max_possible_savings = 0
salary = startingsalary
for _ in range(36):
    max_possible_savings += (salary / 12) + (max_possible_savings * rmonthly)
    if (_ + 1) % 6 == 0:
        salary *= (1 + semiannualraise)
if max_possible_savings < downpayment - epsilon:
    print("It is not possible to pay the down payment in three years.")
else:
    high = 10000
    low = 0
    step = 0
    portion_of_salary = 0

    while True:
        nummonths = 0
        salary = startingsalary
        savings = 0  # 每次迭代重置储蓄
        # 先确定当前要测试的储蓄率，固定值
        portion_of_salary = bisection(low, high) / 10000
        step += 1

        # 用固定储蓄率计算36个月的储蓄
        while nummonths < 36:
            savings += (salary / 12 * portion_of_salary) + (savings * rmonthly)
            nummonths += 1
            if nummonths % 6 == 0:
                salary *= (1 + semiannualraise)
        
        # 判断是否符合条件
        if abs(downpayment - savings) <= epsilon:
            break
        elif downpayment - savings > epsilon:
            # 储蓄不够，需要提高储蓄率
            low = portion_of_salary * 10000
        else:
            # 储蓄过多，降低储蓄率
            high = portion_of_salary * 10000

    print(f"Best savings rate: {portion_of_salary * 100:.4f}%")
    print(f"Steps in bisection search: {step}")

关键修正点说明 #

• 每次二分迭代前重置savings，确保每次计算的都是当前储蓄率下的独立结果
• 把portion_of_salary的计算移到内层36个月循环外面，保证整个周期用同一个储蓄率测试
• 增加了「最大可能储蓄」的预判断，避免工资过低时无限循环
• 调整了终止条件的判断逻辑，用绝对值判断是否在误差范围内，更严谨

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