java - Java-搜索数组中最后一次出现的元素的最佳方法是什么？

Question

我正在写这个方法：findLastOccurrence(Object item) {}

在已排序的对象数组中查找最后一次出现项之后的索引。此方法是较大数据结构的一部分，该数据结构将比较器传递给参数，因此对象始终是可比较的。我想以最有效的方式做到这一点，但我不确定线性方法或使用二进制搜索的方法是否会更快。如果有人可以向我展示他们推荐的这种方法的实现，将不胜感激。

Answer 1

这取决于数组中数据的类型。如果项目经常重复并且更有可能最后一次出现在 (array.length - log_2(array.length)) 位置或更接近末尾 - 线性搜索会更好。否则 - 使用二进制搜索。

此外，您可以考虑数据局部性 - 二进制搜索需要访问数组中的随机元素，并且可以访问比线性搜索更多的缓存行 - 但它也取决于您想要存储在那里的数据类型。

如果您不确定 - 使用二进制搜索。

编辑：实际上在考虑了这个问题之后，线性搜索（step = 1）会比每次迭代后步长增加的搜索更糟糕 - 就像二进制搜索向后运行 - 检查元素：（n-1）-1，（n-1 )-(1+2),(n-1)-(1+2+4), ... (n-1)-(2^k) 如果找到较小的值，则在 (n-1) 之间运行二进制搜索)-(2^k) 和 (n-1)-(2^(k-1))。