php - 如何从一组数字中找到数字的上限和下限？

Question

1st number:  50
2.           30
3.           70
4.           40
5.           11

其他数字是33

我需要计算最后一个数字介于哪两个数字之间(使用 php).. 有什么帮助吗？

Answer 1

遍历列表并找到以下两个值:

• 小于目标数的最大数。
• 大于您的目标数字的最小数字。

在伪代码中:

lowerlimit = Unknown
upperlimit = Unknown
for each n in list:
    if (n <= target) and (lowerlimit is Unknown or n > lowerlimit):
        lowerlimit = n
    if (n >= target) and (upperlimit is Unknown or n < upperlimit):
        upperlimit = n

那么 lowerlimit 和 upperlimit 就是你的答案。该算法需要 O(n) 的时间和 O(1) 的额外空间。

如果你要用许多不同的目标数字测试同一个列表，那么首先需要 O(n log(n)) 时间对列表进行排序可能是有意义的，但是你可以在 O(log (n)) 时间使用二分查找。