删帖吧

xyfree

滚

三月廿七

二分呗

bruceteen

up楼上，排序后二分

KBTiller

楼主是想回避指针运算的未定义行为吧

xyfree

滚

sytpb

再详细些 题目。

OwnWaterloo

回复 5# xyfree

怎么会很久？ 32位（暂不考虑特大内存使用接口）不重叠的区间最多2^32个，最多32次比较。

想要更快就需要内存区间有特殊要求了。比如：
1. 区间大小都是N
2. 起始地址都是N的整数倍
3. 要查询的指针一定在某个区间中 —— 即不需要判断是否确实在某个区间
直接取模就完了。

如果将条件1换成区间大小都是N的整数倍， 可以将区间划分为大小为N的若干个， 每个都保存相同的信息表示是从同一区间划分得到的。

貌似你都已经有实现的样子？

bruceteen

我考虑过用二分，但并不是所有区间的地址范围都是连在一起的，可能是有空隙的，

某些情况下，所要查询的地址如果是落在空隙中的话，简单的二分法要很久才能查到。

二分不是不好，但至少要对这个case做一点优化设计吧？
xyfree 发表于 2011-09-28 08:45

    我听不懂，为什么“所要查询的地址如果是落在空隙中的话，简单的二分法要很久才能查到”？
我举个例子吧，你的区间是[100,200), [300,400), [500,1000)
排序一下得到集合 { 100, 200, 300, 400, 500, 1000 }
假设你搜索 350，得到一个下标索引2，因为2为偶数，所以结论是：350在第（2/2=1）个区间，这个区间的范围是p[2]到p[2+1]
假设你搜索 450，得到一个下标索引3，因为3为奇数，所以结论是：450落在第（3/2=1）个区间到第（(3+1)/2=2）个区间之间

xyfree

滚

prc

为什么需要很久？
在2^32的地址空间内，查找次数不会超过32次
如果是2^64，也不会超过64次