2
我有一組不相交的整數區間,並要檢查一個給定的整數是否位於這些區間中的一個。當然,這可以通過在對數時間進行二分搜索來實現。然而,絕大多數查詢返回false
,即只有非常少的整數位於任何區間。爲了加速應用程序,我正在尋找一種概率,恆定時間算法(某種散列函數),告訴我給定的整數是否肯定不是或可能在一個區間內。這裏是預期的算法,其中magic_data_structure
與存儲在tree
間隔被初始化的草圖:高效的數據結構
x = some_integer;
if(!magic_data_structure.find(x))
return false; // definitely not in any interval
return tree.find(x); // binary search on tree
文學任何想法或提示?非常感謝您的幫助!
P.S .:是否有人知道間隔樹的改進?非重疊間隔(與上述不同)可能包括其他間隔?