索引元素的快速反向查找
索引元素的快速反向查找
提问于 2013-12-05 00:58:21
我的问题是如何在索引中进行反向查找的情况下提高性能。我有一个有序的对象列表，这些对象必须在概念上被分成几个类别。在创建并需要存储列表时，检索每个类别起始位置的索引。当我给出有序列表的索引并需要知道它属于哪个类别时，查找会在后面进行。
在我目前的方法中，我有两个有序列表:一个包含元素，另一个包含类别的索引。
List<Object> data = { "df", "sdfgbh", "sgdadF", "dfdF", "dFADF", "adfadf", "Dafadf", "dafadf", "654654", "sfgsfgsfg", "ethdgh", "fgnfghfgh", "fghsdfgh", "54654", ...up to 1000 }
List<Integer> categories = { 50, 146, 222, 345, 475, 610, 824, 968 }当尝试查找索引i的类别时，该算法的性能为O(n)
public int categoryIndex(int position) {
for (Integer i: categories){
if (i > position) return i;
}
return 0;
}有没有比二分查找更好的方法来解决这个问题呢？
回答 1
Stack Overflow用户
发布于 2013-12-05 01:08:57
除了加长data列表和执行直接索引查找(这将只占用每个元素1个指针的内存，因此对于包含1000个元素的列表来说只有4k左右-至少是可行的)，二进制搜索至少需要O(log(n))时间。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/20381388
复制相关文章
相似问题
腾讯云开发者
