algorithm - 如何有效地找到数字属于哪个范围？

Question

我在求职面试中被问到以下问题:

Given a graduated income tax system as follows:

• Up to 10000 is taxed at 10%

• 10001 to 50000 is taxed at 20%

• 50001 and above is taxed at 30%

Write a program to calculate the taxes on a given income.

Example:

• Taxes on 15000 would be (20% of 5000 + 10% of 10000) = 2000

• Taxes on 60000 would be (30% of 10000 + 20% of 40000 + 10% of 10000) = 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 次，每次都可能扫描整个列表。

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

Answer 1

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

我还删除了 Dillon Davis 在评论中注意到的过多的上限，并将较低的值更改为先前范围的末尾以使公式更加精确

 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

或者(使用 Dillon Davis 的建议)

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

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

整体复杂度是线性或对数的(有 BS)