如何在分区间隔中获取值所属的分区？

Question

我有间隔,分区为大量较小的分区.

没有任何空格也没有任何重叠的间隔.

例如:(0;600)分为:

1. (0;10>
2. (10;25>
3. (25;100>
4. (100;125>
5. (125;550>
6. (550;600)

现在我有大量的值,我需要获得每个值的分区ID.我可以存储将此区间划分为更小间隔的值数组.但是如果所有值都属于最后一个分区,那么它需要通过整个数组.

所以我正在寻找存储这些间隔的更好的解决方案.我想简单 - 最大cca 150行长度算法,我不想使用除std之外的任何库.

Answer 1

由于分区中没有"空格",因此每个分区的末尾都是冗余的(它与下一个分区的开头相同).

由于您对分区列表进行了排序,因此您可以简单地使用二进制搜索std::upper_bound.

看到它在行动.

编辑:更正(upper_bound,不是lower_bound).