刪帖吧

xyfree

滾

三月廿七

二分唄

bruceteen

up樓上，排序后二分

KBTiller

樓主是想回避指針運算的未定義行為吧

xyfree

滾

sytpb

再詳細(xì)些 題目。

OwnWaterloo

回復(fù) 5# xyfree

怎么會很久？ 32位（暫不考慮特大內(nèi)存使用接口）不重疊的區(qū)間最多2^32個，最多32次比較。

想要更快就需要內(nèi)存區(qū)間有特殊要求了。比如：
1. 區(qū)間大小都是N
2. 起始地址都是N的整數(shù)倍
3. 要查詢的指針一定在某個區(qū)間中 —— 即不需要判斷是否確實在某個區(qū)間
直接取模就完了。

如果將條件1換成區(qū)間大小都是N的整數(shù)倍， 可以將區(qū)間劃分為大小為N的若干個， 每個都保存相同的信息表示是從同一區(qū)間劃分得到的。

貌似你都已經(jīng)有實現(xiàn)的樣子？

bruceteen

我考慮過用二分，但并不是所有區(qū)間的地址范圍都是連在一起的，可能是有空隙的，

某些情況下，所要查詢的地址如果是落在空隙中的話，簡單的二分法要很久才能查到。

二分不是不好，但至少要對這個case做一點優(yōu)化設(shè)計吧？
xyfree 發(fā)表于 2011-09-28 08:45

    我聽不懂，為什么“所要查詢的地址如果是落在空隙中的話，簡單的二分法要很久才能查到”？
我舉個例子吧，你的區(qū)間是[100,200), [300,400), [500,1000)
排序一下得到集合 { 100, 200, 300, 400, 500, 1000 }
假設(shè)你搜索 350，得到一個下標(biāo)索引2，因為2為偶數(shù)，所以結(jié)論是：350在第（2/2=1）個區(qū)間，這個區(qū)間的范圍是p[2]到p[2+1]
假設(shè)你搜索 450，得到一個下標(biāo)索引3，因為3為奇數(shù)，所以結(jié)論是：450落在第（3/2=1）個區(qū)間到第（(3+1)/2=2）個區(qū)間之間

xyfree

滾

prc

為什么需要很久？
在2^32的地址空間內(nèi)，查找次數(shù)不會超過32次
如果是2^64，也不會超過64次