由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - 这是什么算法?
相关主题
一道算法题求教,以前用git 现在得用hg 学的好头疼
算法求教请教有没有这样的工具
问一道面试题, 关于算法 (转载)About Longest repeated substring
这道题贴过没有?问个矩阵问题
越南问题 谁做出来了?问一个数据结构面试问题
Scala又被鄙视了请教SQL大拿
收集code 片段的软件有没有网站能计算给定的2个经纬度的距离? (转载)
我们造轮子吧,轮子成败的关键应该是[合集] 问个面试题
相关话题的讨论汇总
话题: 算法话题: tree话题: 99话题: index
进入Programming版参与讨论
1 (共1页)
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).

1 (共1页)
进入Programming版参与讨论
相关主题
[合集] 问个面试题越南问题 谁做出来了?
随机数与概率Scala又被鄙视了
大家帮我回忆一下,以前在这里遇见的一个题目收集code 片段的软件
C++ code explanation我们造轮子吧,轮子成败的关键应该是
一道算法题求教,以前用git 现在得用hg 学的好头疼
算法求教请教有没有这样的工具
问一道面试题, 关于算法 (转载)About Longest repeated substring
这道题贴过没有?问个矩阵问题
相关话题的讨论汇总
话题: 算法话题: tree话题: 99话题: index