c – 用于查找包含数字的非重叠范围的高效数据结构

发布时间：2020-12-16 09:39:10 所属栏目：百科来源：网络整理

导读：用于存储范围的起点和终点的数据结构. rangename start endrange1 10 11range2 20 22range3 0 5 现在,如果我必须找到数字’x’可能存在的范围. 在c中存储这个的有效方法是什么？我正在尝试使用地图.但然后搜索找到范围可能是昂贵的(我不确定).建议一个好的

用于存储范围的起点和终点的数据结构.

rangename      start     end

range1          10        11

range2          20        22

range3          0         5

现在,如果我必须找到数字’x’可能存在的范围.

在c中存储这个的有效方法是什么？

我正在尝试使用地图.但然后搜索找到范围可能是昂贵的(我不确定).建议一个好的数据结构.

我应该能够找到元素是否存在于范围内.范围不应混合和匹配,也不应相邻或其他边界.

如果我需要找到一个元素3,它存在于范围3中,但是元素12根本不存在.只是循环通过不是一种有效的方式.

解决方法

(我已经改变了这个答案,因为提问者澄清了他的范围不重叠.)

如果范围集没有改变,您可以使用排序向量和二分搜索,如ravenspoint的答案中所建议的那样.

如果范围集随时间而变化,您可能仍然使用已排序的向量,或者您可能希望使用std :: map.在这种情况下,您需要尝试两者并查看哪一个更快.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!