如何在分區間隔中獲取值所屬的分區？

沒有任何空格也沒有任何重疊的間隔。

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

回答