我有一个直接缓冲液保持已排序的整数（即1,1,3,3,3,3,7,7，....）。大多数值将会出现多次。我想找到我寻找的价值观的第一个位置。如何在Java中高效搜索排序的巨大直接缓冲区？
如果不是，有什么搜索算法会建议执行，因为：
编辑：感谢所有的海报暗示Arrays.binarySearch()，但是，据我所知，直接缓冲区一般不具有支持数组。这就是为什么我正在寻找一个直接在缓冲区上工作的实现。
而且，可能会出现高达一千倍的每个值，因此找到一个着陆点之后的线性搜索可能不会是非常有效的。但dasblinkenlight的比较建议可能会起作用。
最好的方法是编写自己的执行Binary Search的缓冲区。这种方法小心避免了与创建视图，复制大型数组等相关的潜在性能命中，并且同时保持紧凑。
在链路的代码示例返回最右边的点;你需要在nums[guess] > check符合>=更换>得到最左边的点。这可以为您节省昂贵的后向线性搜索，或使用“向后”Comparator，这需要将您的int包装到Integer对象中。
谢谢。如果没有已经实施的图书馆，那就是我要做的。 – 2012-03-30 14:43:37
@SeNorm有几个库已经实现，但是将其适配到“Buffer”所需的小小调整可能会严重影响性能。由于实施只有十几行，实现“定制”并节省大量成本几乎为零。 – dasblinkenlight 2012-03-30 14:45:38
如果表现的确如你在问题中所说的那样至关重要，那么“重新发明轮子”就足够了。 – biziclop 2012-03-30 14:47:10
我不知道缓冲区的内置功能（Arrays.binarySearch(...)需要将缓冲区转换为数组），但至于3：因为缓冲区已经排序，二进制搜索可能会有用。如果您发现该值，则可以检查以前的值以获取该序列的开始。
ByteBuffer buffer = createByteBuffer();
IntBuffer intBuffer = buffer.asIntBuffer();
如果字节数组可以被转换成int数组使用：
int [] array = intBuffer.array();
int index = java.util.Arrays.binarySearch(array,7);
您可能想提及'intBuffer.array（）'是一个可选操作。 – dasblinkenlight 2012-03-30 14:24:09
这将需要额外的反向线性搜索来获得序列的开始，因为二分查找并不能保证返回第一个元素。 – Thomas 2012-03-30 14:25:15
请参阅java.util.Arrays.binarySearch - 您可以将此代码用于您的。用intBuffer.get替换array [i] – 2012-03-30 14:33:35
您可能必须编写自己的二进制搜索：如果选中的值等于搜索到的值，则始终向左移动。
那么有效，而不是x，你要去寻找x-ε。您的算法将始终采用完全logn（或logn + 1）的步骤，因为它总是会“失败”，但会为您提供大于x-ε的第一个元素的索引。所有你需要做的就是检查该元素是否为x，如果是，你找到了你的匹配，如果不匹配，你的缓冲区中没有x。
'Arrays.binarySearch'会诀窍吗？拥有数百万条记录，它应该在不到三十步的情况下为您提供答案。您可能需要提供自定义比较器来获取第一个位置，而不是最后一个位置。 – dasblinkenlight 2012-03-30 14:16:40
我会使用二进制搜索来查找一个数字，然后开始向左直线搜索，直到获得第一个出现的那个数字 – 2012-03-30 14:17:54
@dasblinkenlight只使用binarySearch将永远不会工作。因为这里的数字是重复的，提问者希望数字的第一次出现。 – 2012-03-30 14:18:40