Dav*_*ave 8 language-agnostic algorithm data-structures
给定n个非负整数的无序列表(不保证分布或重复),我希望能够给出一个可能不在列表中的整数,并且使用列表中至少那么大的整数来响应.我有n ^ 2预处理时间,最多n*log(n)存储.这可能吗？
我的不太好的解决方案是二进制搜索(log n time,constant space).
在地图中存储所有可能查询的地图会占用太多存储空间.
编辑:需要对输入进行一些假设的部分解决方案,例如整数的分布或最大大小,也很有用.
编辑:这被称为前任/后继问题.有一篇Beame&Fich的论文,他们构建了一个数据结构,它存储来自O(n)空间中大小为N的宇宙的n个整数元素集,并在O中执行前导查询(min {(log log N)/(log) log log N),sqrt(log n /(log log n))})时间.
http://homes.cs.washington.edu/~beame/papers/stocpred.pdf
编辑 - 赏金:今天早上的答案都不是我正在寻找的.N没有界限.整数不一定低于32位.最大元素可能比元素数量大得多.我假设没有分配输入.在现有的答案中,我接受了Coffin的赏金,因为它涵盖了我确实有分布的相对较大的问题子集.
假设您的元素相当均匀地分布（或至少相当紧密地遵循某种分布），明显的方法是对数据进行排序，然后使用插值搜索而不是二分搜索。
插值搜索通常具有大约 O(log log n) 的复杂度。
哦，如果从名称上看不出来，插值搜索的基本思想是使用插值来猜测您正在搜索的元素的大致位置。例如，如果您正在处理 0 到 100,000 之间的整数，并且需要查找 21,000，则可以从数组中大约 21% 的位置开始，而不是从中间点开始。然后，根据您在那里找到的值，您可以使用插值来找到更好的猜测，依此类推。
该示例适用于线性插值，但相同的基本思想也适用于其他分布 - 您只需使用与数据分布（相当好）拟合的函数即可。