G***G 发帖数: 16778 | 1 一组区间数
(1,3)
(5,7)
(8,10)
(11,100)
(1000,2000)
.....
给定一个值99,请问,如何快速知道99是落在(11,100)之间.
这个算法叫什么?谢谢! | b**g 发帖数: 335 | 2 binary search?
【在 G***G 的大作中提到】 : 一组区间数 : (1,3) : (5,7) : (8,10) : (11,100) : (1000,2000) : ..... : 给定一个值99,请问,如何快速知道99是落在(11,100)之间. : 这个算法叫什么?谢谢!
| G***G 发帖数: 16778 | 3 我不是查一个数值
比如:1,2,3,4,5,中查找3
而是,把一个值扔到区间中.
【在 b**g 的大作中提到】 : binary search?
| s****u 发帖数: 118 | 4 结果集可能是全部,直接O(n)好了,有什么好快速的
【在 G***G 的大作中提到】 : 一组区间数 : (1,3) : (5,7) : (8,10) : (11,100) : (1000,2000) : ..... : 给定一个值99,请问,如何快速知道99是落在(11,100)之间. : 这个算法叫什么?谢谢!
| c*****t 发帖数: 1879 | 5 In your case, all the intervals are disjoint, a simple binary earch
mechanism is enough to solve this issue (i.e. just check the even/odd
of array index)
For overlapping ones, the best solution is the interval tree.
Some other algorithms that have slightly longer constant are R
tree, or search trees built on top of GiST (which would be a nice
index scheme for database).
【在 G***G 的大作中提到】 : 一组区间数 : (1,3) : (5,7) : (8,10) : (11,100) : (1000,2000) : ..... : 给定一个值99,请问,如何快速知道99是落在(11,100)之间. : 这个算法叫什么?谢谢!
| G***G 发帖数: 16778 | 6 My case is not overlapping.
【在 c*****t 的大作中提到】 : In your case, all the intervals are disjoint, a simple binary earch : mechanism is enough to solve this issue (i.e. just check the even/odd : of array index) : For overlapping ones, the best solution is the interval tree. : Some other algorithms that have slightly longer constant are R : tree, or search trees built on top of GiST (which would be a nice : index scheme for database).
|
|