java - 有效地从数组中获取落在某个范围内的元素

Question

在 Java 中，如果我想从数组中获取落在特定范围内的元素，那么最有效的方法是什么？

例如

数组

A = [25,32,54,23,76,34];

我想得到

element between 45 and 55.

也就是元素:

54

那么获得它的最有效方法是什么？

Answer 1

如果您要重复搜索数组，那么最好的选择是对数组进行排序并使用二进制搜索来查找上下界。当分摊到足够多的搜索时，这将为您提供 O(log n) 性能。

如果它是一次性搜索，除了像其他人建议的那样扫描数组并将每个元素与下限/上限进行比较之外，你不能做得更好 - 这是 O(n)。