java - 如何在 Java 中有效地搜索已排序的、巨大的、直接的缓冲区？

Question

我有一个直接缓冲区，其中包含已排序的整数(即 1,1,3,3,3,3,7,7,....)。大多数值会出现多次。我想找到我搜索的值的第一个位置。

1. 是否有直接使用缓冲区的搜索功能内置Java？ (找不到任何东西)
2. 如果没有，是否有任何像样的库提供此类功能？

3. 如果不是，建议采用哪种搜索算法来实现，前提是:

   • 我的缓冲区中通常会有数百万个条目
   • 速度很重要
   • 它必须返回第一次出现的搜索数字
   • 我不想让它修改数据，因为之后我需要原始数据

编辑:感谢所有建议Arrays.binarySearch() 的海报，但据我所知，直接缓冲区通常没有后备数组。这就是为什么我一直在寻找一个直接在缓冲区上工作的实现。

此外，每个值最多可以出现一千次，因此在找到着陆点后进行线性搜索可能效率不高。不过，dasblinkenlight 的比较器建议可能会奏效。

Answer 1

最好的方法是编写您自己的 Binary Search 实现代码对于缓冲区。这种方法小心地避免了与创建 View 、复制大型数组等相关的潜在性能影响，同时保持紧凑。

链接处的代码示例返回最右边的点；您需要在 nums[guess] > check 行上用 >= 替换 > 以获得最左边的点。这可以为您节省潜在的昂贵的反向线性搜索，或使用“反向”Comparator，这需要将您的 int 包装到 Integer 对象中。