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

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

E.g：(0;600)被分离成：

(0;10>
(10;25>
(25;100>
(100;125>
(125;550>
(550;600)

现在我有大量的值，我需要为他们每个获得分区ID。我可以存储将该间隔分成更小间隔的数组值。但是，如果所有的值都属于最后一个分区，它将需要通过整个数组。

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

2011-10-07 kravemir

那么，基本上，你想我们为你写吗？ –

我不想让你为我写。但请给我一些帮助我的点或算法。 – kravemir

我不明白这一点：当你说（0,10），（10,25）时，10属于哪里？此外，“分区”已经意味着一个详尽的，不重叠的覆盖范围，以便该范围的每个成员都在一个独特的分区集中。所以你的第二句话是多余的。 –

由于分区中没有“空白空间”，因此每个分区的末尾都是多余的（与下一个分区的开始位置相同）。

而且由于您已对分区列表进行排序，因此您可以使用二分查找，并使用std::upper_bound。

编辑：更正（upper_bound，而不是lower_bound）。

2011-10-07 17:52:43 Jon

@Miro：'std :: map'是什么？但总的来说，你可以;还有一个['std :: map :: upper_bound']（http://www.cplusplus.com/reference/stl/map/upper_bound/）方法。 – Jon

因为我需要获取值所属区间的ID。 – kravemir

您可以改善您的搜索算法。

将所有的范围放在数组中，然后使用Binary Search Algorithm来搜索正确的范围。

这将花费O（logn），而且实现起来非常简单。

2011-10-07 17:59:58

我不得不说，根据我的经验，二进制搜索是非常难以正确实施的，这听起来很简单。 :) – Jon

回答