如何高效地找到一个数字属于哪个范围？

Question

我在工作面试中被问到以下问题：

给定分级所得税制度如下：

• 10000 以下按 10% 征税

• 10001 至 50000 按 20% 征税

• 50001及以上按30%征税

编写一个程序来计算给定收入的税收。

例子：

• 15000 的税款为（5000 的 20% + 10000 的 10%）= 2000

• 60000 的税款为（10000 的 30% + 40000 的 20% + 10000 的 10%）= 12000

我想出了以下伪代码：

list = (
    (1, 10000, 0.1)
    (10001, 50000, 0.2)
    (50001, infinity, 0.3)
)

taxableIncome = income
taxes = 0
while taxableIncome > 0
    find e in list such that taxableIncome is in range [e[1], e[2]]
    taxes += taxableIncome - e[1] + 1
    taxableIncome = e[1] - 1

return taxes

上面的方法有效，但在最坏的情况下需要列表中项目数量的二次方时间。考虑收入 = 60000 的情况；该代码循环 3 次，每次都可能扫描整个列表。

有没有更快的方法来找出收入属于哪个范围？这个问题有一些Python解决方案，但我对通用算法解决方案感兴趣，而不是库。

Answer 1

预先计算每个范围开始的税值并将该值包含在列表中。

此外，正如狄龙·戴维斯在评论中注意到的那样，我删除了过高的上限，并将较低的值更改为先前范围的末尾，以使公式更加精确

 list = (
        (0, 0, 0.1)
        (10000, 1000, 0.2)
        (50000, 9000, 0.3)
    )

对于给定的收入，通过线性搜索（如果范围数量很小）或二分搜索（如果范围很多 - 几十个、几百个等）找到适当的范围

然后用简单的公式计算税金

  tax  = e[2] + (income - e[1]) * e[3]

对于收入15000我们可以找到

range = 2nd interval (10000, 1000, 0.2)
tax = 1000 + (15000 - 10000) * 0.2 = 
      1000 + 5000 * 0.2 = 2000

或者（使用狄龙·戴维斯的建议）

  tax  = income * e[3] + (e[2] -  e[1]) * e[3])
  tax  = income * e[3] + e[2]'

e2' = (e[2] - e[1]) * e[3])每个范围都有预先计算的 值

总体复杂度是线性或对数的（带BS）